#1108625 (C++23) No.5022 XOR Printer

• 問題: 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;
}