結果
| 問題 |
No.5022 XOR Printer
|
| ユーザー |
 ぴぃいいいい
|
| 提出日時 | 2025-07-30 00:17:51 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 3 ms / 2,000 ms |
| コード長 | 9,890 bytes |
| コンパイル時間 | 1,201 ms |
| コンパイル使用メモリ | 109,000 KB |
| 実行使用メモリ | 7,716 KB |
| スコア | 5,209,531,981 |
| 最終ジャッジ日時 | 2025-07-30 00:17:55 |
| 合計ジャッジ時間 | 3,682 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <utility>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
// 定数定義
const int GRID_SZ = 10;
const int TOTAL_CELLS = 100;
const int HALF_CELLS = 50;
const int BITS_CNT = 20;
const int EMERG_THRESH = 20;
const int GRID_MAX_IDX = 9;
const int SNAKE_W = 5;
// 操作タイプ
enum Command {
COLLECT = 'C', // 値を取得
WRITE = 'W', // 値を書き込み
UP = 'U', // 上移動
DOWN = 'D', // 下移動
LEFT = 'L', // 左移動
RIGHT = 'R' // 右移動
};
// 座標構造体
struct Position {
int x, y;
Position(int x = 0, int y = 0) : x(x), y(y) {}
// マンハッタン距離を計算
int distance_to(const Position& other) const {
return abs(x - other.x) + abs(y - other.y);
}
};
// グローバル変数
int s; // 現在のスコア状態
int t; // 残り操作回数
int n; // 入力パラメータ
Position cur_pos; // 現在位置
int a[GRID_SZ][GRID_SZ]; // グリッドの値
Position route[TOTAL_CELLS]; // 事前計算されたルート
// 関数宣言
void input();
void move_to(const Position& target);
void exec_cmd(Command cmd);
Position find_nearest_bit_target(int bit);
vector<Position> solve_tsp(const vector<Position>& targets);
// 操作を出力し、操作回数を管理する関数
void exec_cmd(Command cmd) {
putchar(static_cast<char>(cmd));
putchar('\n');
// 残り操作が緊急閾値になったら特別な終了処理
if (--t == EMERG_THRESH) {
Position emerg_pos1(0, 5);
Position emerg_pos2(0, 4);
move_to(emerg_pos1);
exec_cmd(COLLECT);
s ^= a[emerg_pos1.x][emerg_pos1.y];
move_to(emerg_pos2);
exec_cmd(COLLECT);
s ^= a[emerg_pos2.x][emerg_pos2.y];
move_to(emerg_pos1);
exec_cmd(WRITE);
a[emerg_pos1.x][emerg_pos1.y] ^= s;
exit(0);
}
}
// 指定座標に移動する関数
void move_to(const Position& target) {
while (cur_pos.x < target.x) {
++cur_pos.x;
exec_cmd(DOWN);
}
while (cur_pos.x > target.x) {
--cur_pos.x;
exec_cmd(UP);
}
while (cur_pos.y < target.y) {
++cur_pos.y;
exec_cmd(RIGHT);
}
while (cur_pos.y > target.y) {
--cur_pos.y;
exec_cmd(LEFT);
}
}
// インデックスから座標を計算する関数
Position calc_pos(int q) {
if (q >= HALF_CELLS) {
// 後半50個は前半の鏡像
Position pos = calc_pos(q - HALF_CELLS);
return Position(GRID_MAX_IDX - pos.x, GRID_MAX_IDX - pos.y);
} else {
// 前半50個の座標計算（蛇行パターン）
// x軸：UP/DOWN方向、y軸：RIGHT/LEFT方向
int x = q / SNAKE_W;
int y = (q / SNAKE_W % 2) ? (q % SNAKE_W) : (SNAKE_W - 1 - q % SNAKE_W);
return Position(x, y);
}
}
// ステップ1改善: 条件を満たす座標の中で現在地から最も近い座標を選択
Position find_nearest_bit_target(int bit) {
Position best_pos(-1, -1);
int min_distance = INT_MAX;
for (int q = 0; q < TOTAL_CELLS; ++q) {
Position pos = route[q];
if ((s ^ a[pos.x][pos.y]) >> bit == 1) {
int distance = cur_pos.distance_to(pos);
if (distance < min_distance) {
min_distance = distance;
best_pos = pos;
}
}
}
return best_pos;
}
// ルートの総距離を計算
int calculate_total_distance(const vector<Position>& route) {
if (route.size() <= 1) return 0;
int total = cur_pos.distance_to(route[0]); // スタート地点から最初の点まで
for (size_t i = 0; i < route.size() - 1; ++i) {
total += route[i].distance_to(route[i + 1]);
}
return total;
}
// 2-opt改善を実行
bool two_opt_improve(vector<Position>& route) {
bool improved = false;
int n = route.size();
for (int i = 0; i < n - 1; ++i) {
for (int j = i + 2; j < n; ++j) { // j = i + 2 to avoid adjacent edges
// 元の距離
int old_dist = route[i].distance_to(route[i + 1]) + route[j].distance_to(route[(j + 1) % n]);
// 2-opt交換後の距離
int new_dist = route[i].distance_to(route[j]) + route[i + 1].distance_to(route[(j + 1) % n]);
if (new_dist < old_dist) {
// 区間 [i+1, j] を逆順にする
reverse(route.begin() + i + 1, route.begin() + j + 1);
improved = true;
}
}
}
return improved;
}
// TSP解決（貪欲法 + 2-opt局所探索）
vector<Position> solve_tsp(const vector<Position>& targets) {
if (targets.empty()) return vector<Position>();
if (targets.size() == 1) return targets;
vector<Position> result;
vector<bool> visited(targets.size(), false);
// Step 1: 貪欲法で初期解を生成
// 現在地から最も近い点を開始点とする
int current_idx = 0;
int min_distance = INT_MAX;
for (size_t i = 0; i < targets.size(); ++i) {
int distance = cur_pos.distance_to(targets[i]);
if (distance < min_distance) {
min_distance = distance;
current_idx = i;
}
}
visited[current_idx] = true;
result.push_back(targets[current_idx]);
// 貪欲法でTSPを近似的に解く
for (size_t count = 1; count < targets.size(); ++count) {
int next_idx = -1;
min_distance = INT_MAX;
for (size_t i = 0; i < targets.size(); ++i) {
if (!visited[i]) {
int distance = targets[current_idx].distance_to(targets[i]);
if (distance < min_distance) {
min_distance = distance;
next_idx = i;
}
}
}
if (next_idx != -1) {
visited[next_idx] = true;
result.push_back(targets[next_idx]);
current_idx = next_idx;
}
}
// Step 2: 2-opt局所探索で改善（小さなリストのみ、計算時間を制限）
int max_iterations = 10000; // 反復回数制限で時間を制御
for (int iter = 0; iter < max_iterations; ++iter) {
if (!two_opt_improve(result)) {
break; // これ以上改善できない場合終了
}
}
return result;
}
// 入力を受け取る関数
void input() {
// 入力読み込み
cin >> n >> t;
// 入力はa[行][列]で読み込み、a[x][y]として格納
// x軸：UP/DOWN方向（行）、y軸：RIGHT/LEFT方向（列）
for (int i = 0; i < GRID_SZ; ++i) {
for (int j = 0; j < GRID_SZ; ++j) {
cin >> a[i][j]; // a[x][y] = a[行][列]
}
}
}
int main() {
input();
// ルートの事前計算
for (int q = 0; q < TOTAL_CELLS; ++q) {
route[q] = calc_pos(q);
}
// ビット位置ごとの処理（上位ビットから）
for (int b = BITS_CNT - 1; b >= 0; --b) {
fprintf(stderr, "b=%d\n", b);
// ステップ1改善: ビットbを立てるための値を探す（最近傍選択）
Position target_pos = find_nearest_bit_target(b);
if (target_pos.x != -1) { // 有効な座標が見つかった場合
move_to(target_pos);
exec_cmd(COLLECT);
s ^= a[target_pos.x][target_pos.y];
}
// ビットbが立っていない場合はスキップ
if ((s >> b) != 1) {
continue;
}
// ステップ3改善: ビットbが0の箇所を列挙してTSPで最適化
vector<Position> write_targets;
for (int q = 0; q < TOTAL_CELLS; ++q) {
Position pos = route[q];
if (pos.x >= 0 && pos.x < GRID_SZ && pos.y >= 0 && pos.y < GRID_SZ) {
if (!(a[pos.x][pos.y] >> b & 1)) {
write_targets.push_back(pos);
}
}
}
// TSPで最適な巡回順序を決定（タイムアウト対策として、大きなリストは制限）
if (write_targets.size() > 0 && write_targets.size() <= 50) {
vector<Position> optimal_order = solve_tsp(write_targets);
// 最適順序でWRITE操作を実行
for (const Position& pos : optimal_order) {
if (t <= EMERG_THRESH) break; // 緊急閾値チェック
move_to(pos);
exec_cmd(WRITE);
a[pos.x][pos.y] ^= s;
}
} else {
// フォールバック: 元のアルゴリズムを使用
for (int q = 0; q < TOTAL_CELLS; ++q) {
Position pos = route[q];
if (pos.x >= 0 && pos.x < GRID_SZ && pos.y >= 0 && pos.y < GRID_SZ) {
if (!(a[pos.x][pos.y] >> b & 1)) {
if (t <= EMERG_THRESH) break;
move_to(pos);
exec_cmd(WRITE);
a[pos.x][pos.y] ^= s;
}
}
}
}
// 特定位置での追加処理
if (b < BITS_CNT - 1) {
int idx = TOTAL_CELLS - (BITS_CNT - 1 - b);
Position pos = route[idx];
move_to(pos);
exec_cmd(WRITE);
a[pos.x][pos.y] ^= s;
exec_cmd(COLLECT);
s ^= a[pos.x][pos.y];
}
}
return 0;
}