結果
| 問題 |
No.5022 XOR Printer
|
| ユーザー |
 prussian_coder
|
| 提出日時 | 2025-07-25 11:44:46 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,457 ms / 2,000 ms |
| コード長 | 31,948 bytes |
| コンパイル時間 | 5,594 ms |
| コンパイル使用メモリ | 261,716 KB |
| 実行使用メモリ | 318,208 KB |
| スコア | 5,227,012,591 |
| 最終ジャッジ日時 | 2025-07-26 12:45:11 |
| 合計ジャッジ時間 | 73,542 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
#pragma GCC optimize "-O3,omit-frame-pointer,inline,unroll-all-loops,fast-math"
#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
#include <random>
#include <limits>
#include <cmath>
#include <numeric>
#include <optional>
#include <iterator>
#include <unordered_set>
#include <functional>
using namespace std;
// Random number generator with fixed seed
static mt19937 rng(0);
static uniform_real_distribution<double> uniDist(0.0, 1.0);
// Constants
constexpr int MAX_BIT = 20;
constexpr int MAX_SEE_BIT = 4;
constexpr int DEFAULT_TARGET_BIT = 19;
constexpr double ANNEALING_DECAY = 0.99;
constexpr double INITIAL_ACCEPT_PROB = 0.8;
constexpr int BEAM_WIDTH = 10;
constexpr int MAX_TRIAL = 20;
constexpr int MAX_TRIAL_LAST = 50;
constexpr int MIN_TARGET_BIT = 11; // Use beam search below this
// Global variables
int N, T, N2;
vector<int> board;
vector<int> BINARY_VALS;
int BIT_MASK;
// Forward declarations used by beam search
int manhattan_distance(int pos1, int pos2);
vector<char> generate_move_commands(int start, int end);
//------------------------------------------------------------------------------
// Utility Functions
//------------------------------------------------------------------------------
// 1次元の位置を(x, y)に変換
pair<int, int> to_2d(int pos) {
return { pos / N, pos % N };
}
inline void for_each_near(int pos, const function<void(int)>& f) {
auto [x, y] = to_2d(pos);
for (int dx = -8; dx <= 8; ++dx) {
int nx = x + dx;
if (nx < 0 || nx >= N) continue;
int rem = 8 - abs(dx);
for (int dy = -rem; dy <= rem; ++dy) {
int ny = y + dy;
if (ny < 0 || ny >= N) continue;
f(nx * N + ny);
}
}
}
//------------------------------------------------------------------------------
// Beam search borrowed from sol7.cpp (simplified for reuse)
//------------------------------------------------------------------------------
struct BeamState {
vector<int> board;
int s, pos, turn, score, prev_c_cnt;
BeamState* prev_state;
pair<char,int> prev_action;
BeamState(
const vector<int>& b,
int st,
int p,
int t,
int sc
) : board(b), s(st), pos(p), turn(t), score(sc), prev_c_cnt(0),
prev_state(nullptr), prev_action({'?',0}) {}
};
inline bool beam_state_valid(const BeamState* st, int limit) {
if (st->turn == limit) return true;
int mask = (1 << 19) - 1;
for (int v : st->board) {
mask &= v;
if (mask == 0) return true;
}
return false;
}
inline int beam_last_score(const BeamState* st, int limit) {
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 >= limit) return 0;
return st->score + st->s - min_v;
}
inline vector<char> beam_last_move(const BeamState* 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;
}
class BeamSearchSolver {
static const int BEAM_WIDTH = 80;
static const int STATE_QUE_SIZE = 10;
int limit;
struct PairHash { size_t operator()(uint64_t x) const { return x; } };
public:
explicit BeamSearchSolver(int lim) : limit(lim) {}
BeamState* process(const vector<int>& init_board, int init_s, int init_pos) {
static BeamState* states[STATE_QUE_SIZE][BEAM_WIDTH];
static int sizes[STATE_QUE_SIZE];
for (int i = 0; i < STATE_QUE_SIZE; ++i) sizes[i] = 0;
auto cmp = [](BeamState* a, BeamState* b) { return a->score > b->score; };
BeamState* initial = new BeamState(
init_board, init_s, init_pos, 0,
accumulate(init_board.begin(), init_board.end(), 0)
);
states[0][0] = initial;
sizes[0] = 1;
push_heap(&states[0][0], &states[0][0] + 1, cmp);
int best_score = 0;
BeamState* best_state = nullptr;
for (int turn = 0; turn < limit; ++turn) {
int idx = turn % STATE_QUE_SIZE;
int cur_sz = sizes[idx];
BeamState* cur[BEAM_WIDTH];
for (int i = 0; i < cur_sz; ++i) cur[i] = states[idx][i];
sizes[idx] = 0;
unordered_set<uint64_t, PairHash> seen;
for (int i = 0; i < cur_sz; ++i) {
BeamState* st = cur[i];
uint64_t key = (uint64_t(st->score) << 16) | uint32_t(st->s/1024);
if (!seen.insert(key).second) continue;
for_each_near(st->pos, [&](int v2) {
try_push(st, 'W', v2, states, sizes, cmp);
if (st->prev_c_cnt < 2)
try_push(st, 'C', v2, states, sizes, cmp);
});
}
for (int i = 0; i < cur_sz; ++i) {
int fs = beam_last_score(cur[i], limit);
if (fs > best_score) {
best_score = fs;
best_state = cur[i];
}
}
}
return best_state;
}
private:
void try_push(
BeamState* st,
char key,
int pos,
BeamState* states[][BEAM_WIDTH],
int sizes[],
const function<bool(BeamState*, BeamState*)>& cmp
) {
int dist = manhattan_distance(st->pos, pos);
int next_turn = st->turn + dist + 1;
if (next_turn > limit) 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;
int sz = sizes[idx];
if (sz < BEAM_WIDTH) {
BeamState* ns = apply_move(st, key, pos, next_turn, new_score);
if (beam_state_valid(ns, limit)) {
states[idx][sz] = ns;
++sizes[idx];
push_heap(&states[idx][0], &states[idx][sizes[idx]], cmp);
}
} else if (new_score > states[idx][0]->score) {
BeamState* ns = apply_move(st, key, pos, next_turn, new_score);
if (beam_state_valid(ns, limit)) {
pop_heap(&states[idx][0], &states[idx][BEAM_WIDTH], cmp);
states[idx][BEAM_WIDTH - 1] = ns;
push_heap(&states[idx][0], &states[idx][BEAM_WIDTH], cmp);
}
}
}
BeamState* apply_move(
BeamState* st,
char key,
int pos,
int next_turn,
int new_score
) {
BeamState* ns = new BeamState(*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;
}
};
vector<char> run_beam_search(
const vector<int>& init_board,
int init_s,
int init_pos,
int rem_turn
) {
BeamSearchSolver solver(rem_turn);
BeamState* best = solver.process(init_board, init_s, init_pos);
vector<char> last_actions = beam_last_move(best);
vector<char> actions;
for (BeamState* cur = best; cur->prev_state != nullptr; cur = cur->prev_state) {
auto [key, last_pos] = cur->prev_action;
actions.push_back(key);
auto mv = generate_move_commands(last_pos, cur->pos);
for (auto it = mv.rbegin(); it != mv.rend(); ++it) actions.push_back(*it);
}
reverse(actions.begin(), actions.end());
actions.insert(actions.end(), last_actions.begin(), last_actions.end());
return actions;
}
// (x, y)座標を1次元インデックスへ変換
int to_1d(int x, int y) {
return x * N + y;
}
// マンハッタン距離を求める
int manhattan_distance(int pos1, int pos2) {
auto [x1, y1] = to_2d(pos1);
auto [x2, y2] = to_2d(pos2);
return abs(x1 - x2) + abs(y1 - y2);
}
// startからendまで移動する操作列を生成
vector<char> generate_move_commands(int start, int end) {
vector<char> commands;
auto [x1, y1] = to_2d(start);
auto [x2, y2] = to_2d(end);
int cx = x1;
int cy = y1;
// Vertical moves
while (cx < x2) { commands.push_back('D'); ++cx; }
while (cx > x2) { commands.push_back('U'); --cx; }
// Horizontal moves
while (cy < y2) { commands.push_back('R'); ++cy; }
while (cy > y2) { commands.push_back('L'); --cy; }
return commands;
}
// 移動操作列をコマンドベクタへ追加するヘルパー
void append_move_commands(vector<char>& out, int start, int end) {
auto mv = generate_move_commands(start, end);
out.insert(out.end(), mv.begin(), mv.end());
}
// 操作列を順に適用しボードと状態を更新
void process_board(
vector<int>& b,
const vector<char>& commands,
int& s,
int& pos
) {
for (char c : commands) {
switch (c) {
case 'W': b[pos] ^= s; break;
case 'C': s ^= b[pos]; break;
case 'D': pos += N; break;
case 'U': pos -= N; break;
case 'R': pos += 1; break;
case 'L': pos -= 1; break;
}
}
}
// process_board の逆操作を一手だけ行う
void revert_board(
vector<int>& b,
char c,
int& s,
int& pos
) {
switch (c) {
case 'W': b[pos] ^= s; break;
case 'C': s ^= b[pos]; break;
case 'D': pos -= N; break;
case 'U': pos += N; break;
case 'R': pos -= 1; break;
case 'L': pos += 1; break;
}
}
// start_pos と end_pos を含む長方形領域内の中間点を列挙
vector<int> get_one_intermediate_positions_2d(
int start_pos,
int end_pos
) {
auto [sx, sy] = to_2d(start_pos);
auto [ex, ey] = to_2d(end_pos);
if (sx > ex) swap(sx, ex);
if (sy > ey) swap(sy, ey);
vector<int> candidates;
for (int x = sx; x <= ex; ++x) {
for (int y = sy; y <= ey; ++y) {
if (x != ex || y != ey) {
candidates.push_back(to_1d(x, y));
}
}
}
return candidates;
}
// 1次元移動において2点の中間候補を取得
vector<pair<int, int>> get_two_intermediate_positions_1d(
int start,
int end
) {
int left, right;
if (start <= end) {
left = start;
right = end;
} else {
left = -start;
right = -end;
}
vector<pair<int,int>> result;
for (int m1 = left; m1 <= right; ++m1) {
for (int m2 = m1; m2 <= right; ++m2) {
result.emplace_back(abs(m1), abs(m2));
}
}
return result;
}
// 2次元移動で経由しうる2点の組み合わせを取得
vector<pair<int, int>> get_two_intermediate_positions_2d(
int start_pos,
int end_pos
) {
auto [sx, sy] = to_2d(start_pos);
auto [ex, ey] = to_2d(end_pos);
auto x_pairs = get_two_intermediate_positions_1d(sx, ex);
auto y_pairs = get_two_intermediate_positions_1d(sy, ey);
vector<pair<int,int>> candidates;
for (auto& xp : x_pairs) {
for (auto& yp : y_pairs) {
int pos1 = to_1d(xp.first, yp.first);
int pos2 = to_1d(xp.second, yp.second);
if (pos1 != pos2 && pos2 != end_pos) {
candidates.emplace_back(pos1, pos2);
}
}
}
return candidates;
}
// target_bit のビットが目的範囲に収まっているか判定
bool is_valid_state(int state, int target_bit) {
return (BINARY_VALS[target_bit] <= state &&
state < BINARY_VALS[target_bit + 1]);
}
//------------------------------------------------------------------------------
// RouteOptimizer: 2-opt 山登り法で経路を改良するクラス
//------------------------------------------------------------------------------
class RouteOptimizer {
public:
// 与えられた盤面で target_bit が0のマスを巡回する経路を生成
vector<int> generate_optimal_route(
int start_pos,
const vector<int>& brd,
int target_bit
) {
auto targets = find_target_positions(brd, target_bit);
auto route = build_nearest_neighbor_route(
start_pos,
brd,
move(targets),
target_bit
);
route = apply_2opt_optimization(move(route), brd, target_bit);
return route;
}
private:
// target_bit が0の位置一覧を取得
vector<int> find_target_positions(
const vector<int>& brd,
int target_bit
) {
vector<int> res;
res.reserve(N2);
for (int i = 0; i < N2; ++i) {
if (target_bit <= 17 && ~(brd[i] >> 18) & 1) {
continue;
}
if (((brd[i] >> target_bit) & 1) == 0) {
res.push_back(i);
}
}
return res;
}
// 貪欲法で近傍を順に訪問する経路を構築
vector<int> build_nearest_neighbor_route(
int start_pos,
const vector<int>& brd,
vector<int> targets,
int target_bit
) {
vector<int> route = { start_pos };
int cur = start_pos;
unordered_set<int> rem(targets.begin(), targets.end());
while (!rem.empty()) {
int best = -1;
int bd = numeric_limits<int>::max();
for (int t : rem) {
int d = manhattan_distance(cur, t);
if (d < bd) {
bd = d;
best = t;
}
}
route.push_back(best);
rem.erase(best);
cur = best;
}
adjust_final_position(route, brd, target_bit);
return route;
}
// 最後に回る位置について、target_bitより大きいbit桁が1になるように修正する
void adjust_final_position(
vector<int>& route,
const vector<int>& brd,
int target_bit
) {
for (int i = (int)route.size() - 1; i >= 0; --i) {
if (can_be_final_position(
brd[route[i]],
target_bit
)) {
swap(route[i], route.back());
return;
}
}
}
// 2-opt 法で経路を改良（山登りベースだが、スコア変化が0の場合は低確率で変更許容する）
vector<int> apply_2opt_optimization(
vector<int> route,
const vector<int>& brd,
int target_bit
) {
float acc = INITIAL_ACCEPT_PROB;
int L = route.size();
while (true) {
bool improved = false;
vector<int> idx(L+1);
iota(idx.begin(), idx.end(), 0);
shuffle(idx.begin(), idx.end(), rng);
for (int a = 1; a < L && !improved; ++a) {
for (int b = a + 1; b <= L && !improved; ++b) {
int i = idx[a];
int j = idx[b];
if (i > j) swap(i, j);
if (i == 0) {
continue;
}
if (!is_valid_2opt_move(route, brd, i, j, target_bit)) {
continue;
}
int delta = calculate_2opt_improvement(
route, i, j
);
if (delta < 0 ||
(delta == 0 && uniDist(rng) < acc)) {
reverse(
route.begin() + i,
route.begin() + j
);
improved = true;
}
}
}
if (!improved) {
break;
}
acc *= ANNEALING_DECAY;
}
return route;
}
// 終点との整合性を考慮して 2-opt 移動が妥当か判定
// 終点が最後に回る位置の場合は、target_bitより大きいbit桁が1である必要がある
bool is_valid_2opt_move(
const vector<int>& route,
const vector<int>& brd,
int i,
int j,
int tb
) {
if (j == (int)route.size() &&
!can_be_final_position(
brd[route[i]],
tb
)) {
return false;
}
return true;
}
// 2-opt による距離改善量を計算
int calculate_2opt_improvement(
const vector<int>& route,
int i,
int j
) {
int L = route.size();
if (j == L) {
return manhattan_distance(route[i - 1], route[j - 1]) -
manhattan_distance(route[i - 1], route[i]);
}
return manhattan_distance(route[i - 1], route[j - 1]) +
manhattan_distance(route[i], route[j]) -
manhattan_distance(route[i - 1], route[i]) -
manhattan_distance(route[j - 1], route[j]);
}
// 指定位置を最終地点にできるか判定
bool can_be_final_position(
int cell_val,
int tb
) {
return (tb == DEFAULT_TARGET_BIT) ||
is_valid_state(cell_val ^ BIT_MASK, tb);
}
};
//------------------------------------------------------------------------------
// WriteCopyPlanner: 経路に沿った Write/Copy 操作列を動的計画法で構築する
//------------------------------------------------------------------------------
class WriteCopyPlanner {
public:
// target_bit と探索に用いるビット数を初期化
WriteCopyPlanner(int tb)
: target_bit(tb)
, see_bit(min(tb, MAX_SEE_BIT))
{}
// target_bit未満の上位see_bit桁について、上位から連続して1が立っている数を数える
// Write操作をした際に、target_bit未満の次のbitが1であれば、次のbitを見たときに回らなくて済むのでお得であるため
int count_leading_ones(int v) const {
int cnt = 0;
for (int k = see_bit - 1; k >= 0; --k) {
if (!((v >> k) & 1)) {
break;
}
++cnt;
}
return cnt;
}
// prev_pos→p1→p2→posへ移動する際に、移動中の数字p1,p2を2つ使用してsの値を更新できるか判定
// 2つの数値は、target_bit以上のbit桁が1である必要がある。p1 == prev_posの場合は、p1がp1^sに更新されていることに注意
optional<int> compute_copy_state(
int p1,
int p2,
int prev_pos,
int st,
const vector<int>& brd,
const vector<int>& tops
) const {
int xor1 = brd[p1] ^ BIT_MASK;
int xor2 = brd[p2] ^ BIT_MASK;
if (p1 == prev_pos) {
if (
xor2 >= (1 << target_bit) ||
!is_valid_state(brd[p1] ^ brd[p2], target_bit)
) {
return nullopt;
}
return tops[p1] ^ tops[p2];
}
if (xor1 >= (1 << target_bit) || xor2 >= (1 << target_bit)) {
return nullopt;
}
return st ^ tops[p1] ^ tops[p2];
}
// 経路に沿った最適な Write/Copy コマンド列を生成
vector<char> generate_execution_plan(
const vector<int>& route,
const vector<int>& brd,
int init_state
) {
int L = route.size();
int S = 1 << see_bit;
// DP tables
vector<vector<float>> dp(
L - 1,
vector<float>(S, numeric_limits<float>::infinity())
);
// 復元目的のためにどこから来たかを記録する
vector<vector<tuple<int,int,int>>> tr(
L - 1,
vector<tuple<int,int,int>>(S, { -1, -1, -1 })
);
// 最初のcopy操作について、どのセルを使用したかを記録しておく
vector<int> start_pos(S, -1);
int sp = route[0];
// 現在の地点付近のセルを訪問・コピーし、sのtarget_bitより大きい桁を0、target_bitを1になるようにする
for (int p = 0; p < N2; ++p) {
int xor_val = brd[p] ^ init_state;
if (!is_valid_state(xor_val, target_bit)) continue;
int st =
(xor_val % (1 << target_bit)) >>
(target_bit - see_bit);
int dist =
manhattan_distance(sp, p) +
manhattan_distance(p, route[1]);
if (dp[0][st] > dist) {
dp[0][st] = dist;
start_pos[st] = p;
}
}
// target_bit未満の上位see_bit桁のみDPで考慮する
vector<int> tops(N2);
for (int i = 0; i < N2; ++i) {
tops[i] =
(brd[i] % (1 << target_bit)) >>
(target_bit - see_bit);
}
// DPテーブルを埋める（最終ターンは除く）
for (int i = 1; i < L - 1; ++i) {
for (int st = 0; st < S; ++st) {
if (dp[i - 1][st] == numeric_limits<float>::infinity()) {
continue;
}
// Copy操作せずに移動する場合
{
int val = tops[route[i]] ^ st;
int score = count_leading_ones(val);
float cost = dp[i - 1][st] - score;
if (dp[i][st] > cost) {
dp[i][st] = cost;
tr[i][st] = { st, -1, -1 };
}
}
// route[i-1]→p1→p2→route[i]へ移動する際に、途中のp1,p2を2つをCopyしてsを変更する
if (i > 1) {
for (auto& pr :
get_two_intermediate_positions_2d(
route[i - 1],
route[i]
)) {
auto [p1, p2] = pr;
auto ns = compute_copy_state(
p1,
p2,
route[i - 1],
st,
brd,
tops
);
if (!ns) {
continue;
}
int new_st = *ns;
int val = tops[route[i]] ^ new_st;
int score = count_leading_ones(val);
float cost = dp[i - 1][st] + 2 - score;
if (dp[i][new_st] > cost) {
dp[i][new_st] = cost;
tr[i][new_st] = { st, p1, p2 };
}
}
}
}
}
// 経路を復元する
vector<char> cmds;
int final_idx = L - 2;
int best_st =
min_element(
dp[final_idx].begin(),
dp[final_idx].end()
) - dp[final_idx].begin();
for (int i = final_idx; i >= 2; --i) {
auto [prev_st, p1, p2] = tr[i][best_st];
cmds.push_back('W');
if (p1 < 0) {
append_move_commands(cmds, route[i - 1], route[i]);
} else {
append_move_commands(cmds, p2, route[i]);
cmds.push_back('C');
append_move_commands(cmds, p1, p2);
cmds.push_back('C');
append_move_commands(cmds, route[i - 1], p1);
}
best_st = prev_st;
}
// 最初のcopy操作を追加する
cmds.push_back('W');
int init_pos = start_pos[best_st];
append_move_commands(cmds, init_pos, route[1]);
cmds.push_back('C');
append_move_commands(cmds, route[0], init_pos);
// 経路を逆順にする
reverse(cmds.begin(), cmds.end());
// 最後の移動を追加する
append_move_commands(cmds, route[L - 2], route[L - 1]);
cmds.push_back(
(target_bit == DEFAULT_TARGET_BIT) ? 'W' : 'C'
);
return cmds;
}
private:
int target_bit;
int see_bit;
};
//------------------------------------------------------------------------------
// State: ビームサーチで保持する盤面・位置・操作列
//------------------------------------------------------------------------------
class State {
public:
vector<char> commands;
vector<int> board;
int s;
int pos;
int target_bit;
// 状態を保持する単純なデータコンテナ
State(
const vector<char>& cmds,
const vector<int>& brd,
int state,
int position,
int tb
) : commands(cmds), board(brd), s(state), pos(position), target_bit(tb) {}
// 現在のボード合計を計算
int get_score() const {
return accumulate(board.begin(), board.end(), 0);
}
// 処理手数 - target_bit未満のleading_oneの数
int get_estimated_cost() const {
int cost = commands.size();
for (int val : board) {
for (int b = target_bit - 2; b >= 0; --b) {
if ((val >> b) & 1) {
cost -= 1;
} else {
break;
}
}
}
return cost;
}
};
//------------------------------------------------------------------------------
// Postprocess and Main Solver
//------------------------------------------------------------------------------
// このままでは18ビット目が0であるセルが残ってしまうので、操作終了時にこのセルの値とsの値を交換することで、18ビット目が1になるようにしたい
// 操作列 + この処理を加えた操作（移動操作 + C + W + C + W）がT手以下に収まるようにcmdを戻す
void postprocess_board(
vector<int>& b,
vector<char>& cmds,
int& s,
int& pos
) {
while (true) {
int min_pos =
min_element(b.begin(), b.end()) - b.begin();
int steps =
cmds.size() +
manhattan_distance(pos, min_pos) +
4;
if (steps > T) {
char last_cmd = cmds.back();
cmds.pop_back();
revert_board(b, last_cmd, s, pos);
continue;
}
int best_s = numeric_limits<int>::min();
int best_v = -1;
for (int v : get_one_intermediate_positions_2d(pos, min_pos)) {
int s2 = b[v] ^ s;
if (s2 > best_s) {
best_s = s2;
best_v = v;
}
}
if (best_s < 1000000) {
char last_cmd = cmds.back();
cmds.pop_back();
revert_board(b, last_cmd, s, pos);
continue;
}
// 新しい操作列を追加する
auto mv1 = generate_move_commands(pos, best_v);
append_move_commands(cmds, pos, best_v);
cmds.push_back('C');
auto mv2 = generate_move_commands(best_v, min_pos);
append_move_commands(cmds, best_v, min_pos);
cmds.push_back('W');
cmds.push_back('C');
cmds.push_back('W');
vector<char> recent(
cmds.end() -
(mv1.size() + 1 + mv2.size() + 3),
cmds.end()
);
process_board(b, recent, s, pos);
return;
}
}
// ビームサーチで操作列を生成する
void solve_puzzle() {
int pos = to_1d(0, 0);
int s = 0;
int trial_count;
vector<char> cmds;
vector<State> states = { State(cmds, board, s, pos, MAX_BIT) };
// 上位bit桁から順に、target_bitより大きい桁が1になるように操作列を生成する
for (int tb = MAX_BIT - 1; tb >= MIN_TARGET_BIT; --tb) {
cerr << tb << " " << states[0].commands.size() << endl;
int last_cmd_size = states[0].commands.size();
vector<State> next_states;
for (const auto& state : states) {
if (last_cmd_size > 930) {
trial_count = MAX_TRIAL_LAST;
} else {
trial_count = MAX_TRIAL;
}
for (int trial = 0; trial < trial_count; ++trial) {
vector<char> commands = state.commands;
int current_pos = state.pos;
int current_s = state.s;
vector<int> current_board = state.board;
// routeを生成する
RouteOptimizer ro;
auto route = ro.generate_optimal_route(current_pos, current_board, tb);
// 経路に沿った操作列を生成する
WriteCopyPlanner wcp(tb);
auto exec_cmds =
wcp.generate_execution_plan(route, current_board, current_s);
// 操作列を適用する
process_board(current_board, exec_cmds, current_s, current_pos);
commands.insert(commands.end(), exec_cmds.begin(), exec_cmds.end());
next_states.emplace_back(commands, current_board, current_s, current_pos, tb);
}
}
if (!next_states.empty() && (int)next_states[0].commands.size() > T){
states = next_states;
break;
};
// コストが低い順にソートし、上位BEAM_WIDTH個を選抜する
sort(next_states.begin(), next_states.end(),
[](const State& a, const State& b) {
return a.get_estimated_cost() < b.get_estimated_cost();
});
states.clear();
int keep_count = min(BEAM_WIDTH, (int)next_states.size());
for (int i = 0; i < keep_count; ++i) {
states.push_back(next_states[i]);
}
}
// After main loop, use beam search for remaining turns
int best_score = 0;
vector<char> best_cmds;
for (const auto& state : states) {
board = state.board;
cmds = state.commands;
s = state.s;
pos = state.pos;
int remain = T - (int)cmds.size();
if (remain > 0) {
auto extra = run_beam_search(board, s, pos, remain);
process_board(board, extra, s, pos);
cmds.insert(cmds.end(), extra.begin(), extra.end());
}
postprocess_board(board, cmds, s, pos);
int score = accumulate(board.begin(), board.end(), 0);
if (score > best_score) {
best_score = score;
best_cmds = cmds;
}
}
cmds = best_cmds;
// 出力
for (int i = 0; i < T && i < (int)cmds.size(); ++i) {
cout << cmds[i] << "\n";
}
}
// 入力を読み込み solve_puzzle を呼び出すエントリポイント
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> T;
N2 = N * N;
board.resize(N2);
for (int i = 0; i < N2; ++i) {
cin >> board[i];
}
BINARY_VALS.resize(MAX_BIT + 1);
for (int i = 0; i <= MAX_BIT; ++i) {
BINARY_VALS[i] = 1 << i;
}
BIT_MASK = (1 << MAX_BIT) - 1;
solve_puzzle();
return 0;
}