結果
| 問題 |
No.5022 XOR Printer
|
| コンテスト | |
| ユーザー |
 prussian_coder
|
| 提出日時 | 2025-07-12 11:18:00 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,481 ms / 2,000 ms |
| コード長 | 24,403 bytes |
| コンパイル時間 | 4,615 ms |
| コンパイル使用メモリ | 238,760 KB |
| 実行使用メモリ | 7,720 KB |
| スコア | 5,226,902,255 |
| 最終ジャッジ日時 | 2025-07-26 12:36:22 |
| 合計ジャッジ時間 | 76,569 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / 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>
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 = 8;
constexpr int DEFAULT_TARGET_BIT = 19;
constexpr double ANNEALING_DECAY = 0.99;
constexpr double INITIAL_ACCEPT_PROB = 1.0;
constexpr int BEAM_WIDTH = 8;
constexpr int MAX_TRIAL = 8;
// Global variables
int N, T, N2;
vector<int> board;
vector<int> BINARY_VALS;
int BIT_MASK;
//------------------------------------------------------------------------------
// Utility Functions
//------------------------------------------------------------------------------
// 1次元の位置を(x, y)に変換
pair<int, int> to_2d(int pos) {
return { pos / N, pos % N };
}
// (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
) {
double 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<double>> dp(
L - 1,
vector<double>(S, numeric_limits<double>::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<double>::infinity()) {
continue;
}
// Copy操作せずに移動する場合
{
int val = tops[route[i]] ^ st;
int score = count_leading_ones(val);
double 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);
double 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;
vector<char> cmds;
vector<State> states = { State(cmds, board, s, pos, MAX_BIT) };
// 上位bit桁から順に、target_bitより大きい桁が1になるように操作列を生成する
for (int tb = MAX_BIT - 1; tb >= 0; --tb) {
vector<State> next_states;
for (const auto& state : states) {
for (int trial = 0; trial < MAX_TRIAL; ++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]);
}
if (!states.empty() && (int)states[0].commands.size() > T) break;
}
// 最後に、操作列を戻して、貪欲に得点を伸ばす
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;
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;}