結果
| 問題 |
No.5022 XOR Printer
|
| コンテスト | |
| ユーザー |
 prussian_coder
|
| 提出日時 | 2025-07-15 10:46:12 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 6,686 bytes |
| コンパイル時間 | 2,385 ms |
| コンパイル使用メモリ | 170,620 KB |
| 実行使用メモリ | 814,464 KB |
| スコア | 0 |
| 最終ジャッジ日時 | 2025-07-26 12:40:15 |
| 合計ジャッジ時間 | 7,238 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | MLE * 1 -- * 49 |
ソースコード
#pragma GCC optimize "-O3,omit-frame-pointer,inline,unroll-all-loops,fast-math"
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric> // for accumulate
#include <unordered_set>
#include <cstdint>
#include <utility>
#include <limits>
#include <functional>
using namespace std;
static int N, T;
static int N2;
static vector<vector<int>> NEAR_POS;
inline pair<int,int> to2d(int p) {
return {p / N, p % N};
}
inline int manhattan_distance(int p1, int p2) {
auto [x1,y1] = to2d(p1);
auto [x2,y2] = to2d(p2);
return abs(x1 - x2) + abs(y1 - y2);
}
vector<char> generate_move_commands(int start, int end) {
vector<char> cmds;
auto [x1,y1] = to2d(start);
auto [x2,y2] = to2d(end);
int cx = x1, cy = y1;
while (cx < x2) { cmds.push_back('D'); ++cx; }
while (cx > x2) { cmds.push_back('U'); --cx; }
while (cy < y2) { cmds.push_back('R'); ++cy; }
while (cy > y2) { cmds.push_back('L'); --cy; }
return cmds;
}
struct State {
vector<int> board;
int s, pos, turn, score, prev_c_cnt;
State* prev_state;
pair<char,int> prev_action;
State(const vector<int>& b, int _s, int _pos, int _turn, int _score)
: board(b), s(_s), pos(_pos), turn(_turn), score(_score), prev_c_cnt(0), prev_state(nullptr), prev_action({'?',0}) {}
};
bool state_is_valid(const State* st) {
if (st->turn == T) return true;
int mask = (1 << 19) - 1;
for (int v : st->board) {
mask &= v;
if (mask == 0) return true;
}
return false;
}
int state_last_score(const State* st) {
int min_v = numeric_limits<int>::max();
int min_pos = 0;
for (int i = 0; i < N2; ++i) {
if (st->board[i] < min_v) {
min_v = st->board[i];
min_pos = i;
}
}
int dist = manhattan_distance(st->pos, min_pos);
if (st->turn + dist + 3 >= T) return 0;
return st->score + st->s - min_v;
}
vector<char> state_last_move(const State* st) {
int min_v = numeric_limits<int>::max();
int min_pos = 0;
for (int i = 0; i < N2; ++i) {
if (st->board[i] < min_v) {
min_v = st->board[i];
min_pos = i;
}
}
auto cmds = generate_move_commands(st->pos, min_pos);
cmds.push_back('W');
cmds.push_back('C');
cmds.push_back('W');
return cmds;
}
struct BeamSearchSolver {
const int beam_width = 300;
const int state_que_size = 10;
struct PairHash { size_t operator()(uint64_t x) const { return x; } };
State* process(const vector<int>& init_board) {
vector<vector<State*>> states(state_que_size);
auto cmp = [](State* a, State* b) { return a->score > b->score; };
State* initial = new State(init_board, 0, 0, 0,
accumulate(init_board.begin(), init_board.end(), 0));
states[0].push_back(initial);
push_heap(states[0].begin(), states[0].end(), cmp);
int best_score = 0;
State* best_state = nullptr;
for (int turn = 0; turn < T; ++turn) {
int idx = turn % state_que_size;
auto curr = states[idx];
states[idx].clear();
unordered_set<uint64_t, PairHash> seen;
for (State* st : curr) {
uint64_t key = (uint64_t(st->score) << 32) | uint32_t(st->s);
if (seen.count(key)) continue;
seen.insert(key);
for (int v2 : NEAR_POS[st->pos]) {
try_push(st, 'W', v2, states, cmp);
if (st->prev_c_cnt < 2) try_push(st, 'C', v2, states, cmp);
}
}
for (State* st : curr) {
int fs = state_last_score(st);
if (fs > best_score) {
best_score = fs;
best_state = st;
}
}
}
return best_state;
}
void try_push(State* st, char key, int pos,
vector<vector<State*>>& states,
const function<bool(State*,State*)>& cmp) {
int dist = manhattan_distance(st->pos, pos);
int next_turn = st->turn + dist + 1;
if (next_turn > T) return;
int new_score = (key == 'C' ? st->score
: st->score + ((st->board[pos] ^ st->s) - st->board[pos]));
int idx = next_turn % state_que_size;
auto& q = states[idx];
if ((int)q.size() < beam_width) {
State* ns = apply_move(st, key, pos, next_turn, new_score);
if (state_is_valid(ns)) {
q.push_back(ns);
push_heap(q.begin(), q.end(), cmp);
}
} else if (new_score > q.front()->score) {
State* ns = apply_move(st, key, pos, next_turn, new_score);
if (state_is_valid(ns)) {
pop_heap(q.begin(), q.end(), cmp);
q.pop_back();
q.push_back(ns);
push_heap(q.begin(), q.end(), cmp);
}
}
}
State* apply_move(State* st, char key, int pos, int next_turn, int new_score) {
State* ns = new State(*st);
ns->prev_state = st;
ns->prev_action = {key, st->pos};
ns->turn = next_turn;
ns->score = new_score;
if (key == 'C') {
ns->s ^= st->board[pos];
ns->prev_c_cnt = st->prev_c_cnt + 1;
} else {
ns->board[pos] = st->board[pos] ^ st->s;
ns->prev_c_cnt = 0;
}
ns->pos = pos;
return ns;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> T;
N2 = N * N;
vector<int> board;
board.reserve(N2);
for (int i = 0; i < N2; ++i) {
int x; cin >> x;
board.push_back(x);
}
NEAR_POS.assign(N2, {});
for (int i = 0; i < N2; ++i) {
for (int j = 0; j < N2; ++j) {
if (manhattan_distance(i, j) <= 8) {
NEAR_POS[i].push_back(j);
}
}
}
BeamSearchSolver solver;
State* best = solver.process(board);
vector<char> last_actions = state_last_move(best);
vector<char> actions;
for (State* cur = best; cur->prev_state != nullptr; cur = cur->prev_state) {
auto [key, last_pos] = cur->prev_action;
actions.push_back(key);
auto cmds = generate_move_commands(last_pos, cur->pos);
for (auto it = cmds.rbegin(); it != cmds.rend(); ++it) {
actions.push_back(*it);
}
}
reverse(actions.begin(), actions.end());
actions.insert(actions.end(), last_actions.begin(), last_actions.end());
for (char c : actions) {
cout << c << '\n';
}
return 0;
}