結果
| 問題 |
No.5022 XOR Printer
|
| ユーザー |
 prussian_coder
|
| 提出日時 | 2025-07-09 12:04:18 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,257 ms / 2,000 ms |
| コード長 | 21,371 bytes |
| コンパイル時間 | 5,816 ms |
| コンパイル使用メモリ | 242,108 KB |
| 実行使用メモリ | 7,720 KB |
| スコア | 5,226,576,909 |
| 最終ジャッジ日時 | 2025-07-26 12:34:21 |
| 合計ジャッジ時間 | 66,747 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
//beam searchっぽくしたもの
#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 = 7;
// Global variables
int N, T, N2;
vector<int> board;
vector<int> BINARY_VALS;
int BIT_MASK;
//------------------------------------------------------------------------------
// Utility Functions
//------------------------------------------------------------------------------
pair<int, int> to_2d(int pos) {
return { pos / N, pos % N };
}
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);
}
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 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;
}
}
}
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;
}
}
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;
}
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;
}
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;
}
bool is_valid_state(int state, int target_bit) {
return (BINARY_VALS[target_bit] <= state &&
state < BINARY_VALS[target_bit + 1]);
}
//------------------------------------------------------------------------------
// RouteOptimizer: 2-opt hill climbing with simulated annealing
//------------------------------------------------------------------------------
class RouteOptimizer {
public:
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:
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 (((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;
}
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;
}
}
}
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;
}
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;
}
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: Plans write and copy operations
//------------------------------------------------------------------------------
class WriteCopyPlanner {
public:
WriteCopyPlanner(int tb)
: target_bit(tb)
, see_bit(min(tb, MAX_SEE_BIT))
{}
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 })
);
vector<int> start_pos(S, -1);
int sp = route[0];
// Initialize start states
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;
}
}
// Precompute board top bits
vector<int> tops(N2);
for (int i = 0; i < N2; ++i) {
tops[i] =
(brd[i] % (1 << target_bit)) >>
(target_bit - see_bit);
}
// Fill DP table
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;
}
// Direct write
{
int val = tops[route[i]] ^ st;
int score = [&] (int v) {
int cnt = 0;
for (int k = see_bit - 1; k >= 0; --k) {
if (!((v >> k) & 1)) {
return cnt;
}
++cnt;
}
return cnt;
}(val);
double cost = dp[i - 1][st] - score;
if (dp[i][st] > cost) {
dp[i][st] = cost;
tr[i][st] = { st, -1, -1 };
}
}
// Copy operations
if (i > 1) {
for (auto& pr :
get_two_intermediate_positions_2d(
route[i - 1],
route[i]
)) {
auto [p1, p2] = pr;
optional<int> ns;
int xor1 = brd[p1] ^ BIT_MASK;
int xor2 = brd[p2] ^ BIT_MASK;
if (p1 == route[i - 1]) {
if (
xor2 >= (1 << target_bit) ||
!is_valid_state(
brd[p1] ^ brd[p2],
target_bit
)
) {
continue;
}
ns = tops[p1] ^ tops[p2];
} else {
if (
xor1 >= (1 << target_bit) ||
xor2 >= (1 << target_bit)
) {
continue;
}
ns = st ^ tops[p1] ^ tops[p2];
}
int new_st = *ns;
int val = tops[route[i]] ^ new_st;
int score = [&] (int v) {
int cnt = 0;
for (int k = see_bit - 1; k >= 0; --k) {
if (!((v >> k) & 1)) {
return cnt;
}
++cnt;
}
return cnt;
}(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 };
}
}
}
}
}
// Reconstruct commands
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) {
auto mv = generate_move_commands(
route[i - 1],
route[i]
);
cmds.insert(cmds.end(), mv.begin(), mv.end());
} else {
auto mv2 = generate_move_commands(
p2,
route[i]
);
cmds.insert(cmds.end(), mv2.begin(), mv2.end());
cmds.push_back('C');
auto mv1 = generate_move_commands(p1, p2);
cmds.insert(cmds.end(), mv1.begin(), mv1.end());
cmds.push_back('C');
auto mv0 = generate_move_commands(
route[i - 1],
p1
);
cmds.insert(cmds.end(), mv0.begin(), mv0.end());
}
best_st = prev_st;
}
// Initial writes and copy
cmds.push_back('W');
int init_pos = start_pos[best_st];
auto mv1_start = generate_move_commands(
init_pos,
route[1]
);
cmds.insert(cmds.end(), mv1_start.begin(), mv1_start.end());
cmds.push_back('C');
auto mv0_start = generate_move_commands(
route[0],
init_pos
);
cmds.insert(cmds.end(), mv0_start.begin(), mv0_start.end());
reverse(cmds.begin(), cmds.end());
// Final movement
auto mv_final = generate_move_commands(
route[L - 2],
route[L - 1]
);
cmds.insert(cmds.end(), mv_final.begin(), mv_final.end());
cmds.push_back(
(target_bit == DEFAULT_TARGET_BIT) ? 'W' : 'C'
);
return cmds;
}
private:
int target_bit;
int see_bit;
};
//------------------------------------------------------------------------------
// State: Represents a game state during beam search
//------------------------------------------------------------------------------
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);
}
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
//------------------------------------------------------------------------------
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;
}
// Add new sequence of commands
auto mv1 = generate_move_commands(pos, best_v);
cmds.insert(cmds.end(), mv1.begin(), mv1.end());
cmds.push_back('C');
auto mv2 = generate_move_commands(best_v, min_pos);
cmds.insert(cmds.end(), mv2.begin(), mv2.end());
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) };
for (int tb = MAX_BIT - 1; tb >= 0; --tb) {
vector<State> next_states;
for (const auto& state : states) {
for (int trial = 0; trial < 7; ++trial) {
vector<char> commands = state.commands;
int current_pos = state.pos;
int current_s = state.s;
vector<int> current_board = state.board;
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);
}
}
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;
}
board = states[0].board;
cmds = states[0].commands;
s = states[0].s;
pos = states[0].pos;
postprocess_board(board, cmds, s, pos);
// Output commands
for (int i = 0; i < T && i < (int)cmds.size(); ++i) {
cout << cmds[i] << "\n";
}
// Debug: final board sum
cerr << "final board sum: " << accumulate(board.begin(), board.end(), 0)
<< "\n";
}
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;
}