#1107845 (C++17) No.5022 XOR Printer

• 問題: No.5022 XOR Printer
• ユーザー: mtmr_s1
• 提出日時: 2025-07-26 14:00:04
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 61 ms / 2,000 ms
• コード長: 8,826 bytes
• コンパイル時間: 1,376 ms
• コンパイル使用メモリ: 121,620 KB
• 実行使用メモリ: 7,720 KB
• スコア: 4,921,110,930
• 最終ジャッジ日時: 2025-07-26 14:00:12
• 合計ジャッジ時間: 6,899 ms
• ジャッジサーバーID （参考情報）: judge2 / judge4

ファイルパターン	結果
other	AC * 50

ソースコード

#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <algorithm>
#include <chrono>
#include <random>

using namespace std;

// --- グローバル定数 ---
// 問題の制約に基づいた定数
const int N_CONST = 10;
const int T_CONST = 1000;
// 実行時間制限（ミリ秒）。少しマージンを持たせる
const double TIME_LIMIT_MS = 1950.0; 
// 1つの目的地への経路で試行する乱択の回数
const int NUM_TRIALS = 1000; 
// 後半戦略で「遠い」と判断するマンハッタン距離
const int MIN_DIST_FOR_TARGETING = 5; 

// --- 乱数生成器 ---
// シードを現在時刻で初期化し、実行ごとに異なる乱数系列を生成
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

/**
 * @struct State
 * @brief 現在のゲームの状態を管理する構造体
 */
struct State {
    int r, c;
    int s;
    vector<vector<int>> grid;
    int ops_count;
    string ops_log;

    State(const vector<vector<int>>& initial_grid) {
        r = 0; c = 0; s = 0;
        grid = initial_grid;
        ops_count = 0;
        ops_log = "";
    }

    void apply_op(char op) {
        if (ops_count >= T_CONST) return;
        bool valid = true;
        if (op == 'U') { if (r > 0) r--; else valid = false; }
        else if (op == 'D') { if (r < N_CONST - 1) r++; else valid = false; }
        else if (op == 'L') { if (c > 0) c--; else valid = false; }
        else if (op == 'R') { if (c < N_CONST - 1) c++; else valid = false; }
        else if (op == 'W') { grid[r][c] ^= s; }
        else if (op == 'C') { s ^= grid[r][c]; }
        else { valid = false; }
        if (valid) { ops_count++; ops_log += op; }
    }

    void apply_ops_string(const string& ops) {
        for (char op : ops) { apply_op(op); }
    }
    
    long long calculate_total_score() const {
        long long total_score = 0;
        for(const auto& row : grid) {
            for(int cell_val : row) {
                total_score += cell_val;
            }
        }
        return total_score;
    }
};

// --- ヘルパー関数 ---

/**
 * @brief 2点間の最短経路に対応する移動操作の文字列を生成する
 */
string get_simple_move_ops(int r1, int c1, int r2, int c2) {
    string path_ops = "";
    string vert_move = (r1 < r2) ? "D" : "U";
    string horz_move = (c1 < c2) ? "R" : "L";
    for (int i = 0; i < abs(r1 - r2); ++i) path_ops += vert_move;
    for (int i = 0; i < abs(c1 - c2); ++i) path_ops += horz_move;
    return path_ops;
}

/**
 * @brief 目的地への最適な操作列（移動＋C/W）を乱択で探索する
 * @param current_state 現在の状態
 * @param tr 目的地の行
 * @param tc 目的地の列
 * @return pair<string, long long> 最適な操作列と、それによるスコア増加量
 */
pair<string, long long> find_best_ops_for_target(const State& current_state, int tr, int tc) {
    string move_ops = get_simple_move_ops(current_state.r, current_state.c, tr, tc);
    
    string best_total_ops = move_ops;
    long long best_score_increase = -1;

    for (int i = 0; i < NUM_TRIALS; ++i) {
        string trial_ops = "";
        int temp_s = current_state.s;
        vector<vector<int>> temp_grid = current_state.grid;
        long long current_increase = 0;
        int temp_r = current_state.r;
        int temp_c = current_state.c;

        // 移動経路をシミュレーション
        for(char op : move_ops) {
            trial_ops += op;
            if (op == 'U') temp_r--;
            else if (op == 'D') temp_r++;
            else if (op == 'L') temp_c--;
            else if (op == 'R') temp_c++;

            // --- 経路上での日和見的な書き込み ---
            long long potential_increase = (long long)(temp_grid[temp_r][temp_c] ^ temp_s) - temp_grid[temp_r][temp_c];
            int dist_to_target = abs(temp_r - tr) + abs(temp_c - tc);
            if (potential_increase > 0 && current_state.ops_count + trial_ops.length() + 1 + dist_to_target <= T_CONST) {
                trial_ops += 'W';
                current_increase += potential_increase;
                temp_grid[temp_r][temp_c] ^= temp_s;
            }

            // --- 経路上でのコピー ---
            if (i > 0 && uniform_int_distribution<int>(0, 1)(rng) == 1) {
                 if (current_state.ops_count + trial_ops.length() < T_CONST) {
                    trial_ops += 'C';
                    temp_s ^= temp_grid[temp_r][temp_c];
                 }
            }
        }
        
        // --- 目的地での最終的な書き込み ---
        if (current_state.ops_count + trial_ops.length() < T_CONST) {
            long long final_increase = (long long)(temp_grid[tr][tc] ^ temp_s) - temp_grid[tr][tc];
            if (final_increase > 0) {
                 trial_ops += 'W';
                 current_increase += final_increase;
            }
        }

        if (current_increase > best_score_increase) {
            best_score_increase = current_increase;
            best_total_ops = trial_ops;
        }
    }
    
    if (best_score_increase > 0) {
        return {best_total_ops, best_score_increase};
    } else {
        return {move_ops, -1};
    }
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    auto start_time = chrono::steady_clock::now();

    int N_in, T_in;
    cin >> N_in >> T_in;
    vector<vector<int>> initial_grid(N_CONST, vector<int>(N_CONST));
    for (int i = 0; i < N_CONST; ++i) {
        for (int j = 0; j < N_CONST; ++j) {
            cin >> initial_grid[i][j];
        }
    }

    State current_state(initial_grid);

    vector<pair<int, int>> visit_queue;
    for (int i = 0; i < N_CONST; ++i) {
        for (int j = 0; j < N_CONST; ++j) {
            if (i == 0 && j == 0) continue;
            visit_queue.push_back({i, j});
        }
    }
    shuffle(visit_queue.begin(), visit_queue.end(), rng);

    // --- メインループ: 計画的な訪問 ---
    int visit_idx = 0;
    while (visit_idx < visit_queue.size()) {
        auto current_time = chrono::steady_clock::now();
        double elapsed_ms = chrono::duration_cast<chrono::milliseconds>(current_time - start_time).count();
        if (elapsed_ms > TIME_LIMIT_MS || current_state.ops_count >= T_CONST) {
            break;
        }

        pair<int, int> target_pos = visit_queue[visit_idx];
        pair<string, long long> result = find_best_ops_for_target(current_state, target_pos.first, target_pos.second);
        current_state.apply_ops_string(result.first);
        
        visit_idx++;
    }
    
    // --- デバッグ出力 ---
    cerr << "[DEBUG] Finished initial " << visit_idx << " targets. Ops used: " << current_state.ops_count << endl;


    // --- 後半戦略: スコアの低い遠いマスを狙う ---
    while (true) {
        auto current_time = chrono::steady_clock::now();
        double elapsed_ms = chrono::duration_cast<chrono::milliseconds>(current_time - start_time).count();
        int remaining_ops = T_CONST - current_state.ops_count;

        if (elapsed_ms > TIME_LIMIT_MS || remaining_ops < 2) { 
            break;
        }

        int best_target_r = -1, best_target_c = -1;
        int min_score = -1;

        for (int r = 0; r < N_CONST; ++r) {
            for (int c = 0; c < N_CONST; ++c) {
                int dist = abs(current_state.r - r) + abs(current_state.c - c);
                if (dist == 0 || dist >= remaining_ops) continue;

                bool is_target_candidate = false;
                if (remaining_ops > MIN_DIST_FOR_TARGETING + dist + 5) { // 往復＋αの余裕
                    if (dist >= MIN_DIST_FOR_TARGETING) {
                        is_target_candidate = true;
                    }
                } else { 
                    is_target_candidate = true;
                }

                if (is_target_candidate) {
                    if (best_target_r == -1 || current_state.grid[r][c] < min_score) {
                        min_score = current_state.grid[r][c];
                        best_target_r = r;
                        best_target_c = c;
                    }
                }
            }
        }

        if (best_target_r == -1) break;

        pair<string, long long> result = find_best_ops_for_target(current_state, best_target_r, best_target_c);
        current_state.apply_ops_string(result.first);
    }

    // 最終的な操作ログを改行区切りで出力
    for (char op : current_state.ops_log) {
        cout << op << "\n";
    }

    // --- 最終デバッグ出力 ---
    cerr << "--- Final Debug Info ---" << endl;
    cerr << "Total operations: " << current_state.ops_log.length() << "/" << T_CONST << endl;
    cerr << "Final score: " << current_state.calculate_total_score() << endl;

    return 0;
}