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

• 問題: No.5022 XOR Printer
• ユーザー: mtmr_s1
• 提出日時: 2025-07-26 16:51:45
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 1,993 ms / 2,000 ms
• コード長: 15,530 bytes
• コンパイル時間: 1,928 ms
• コンパイル使用メモリ: 131,048 KB
• 実行使用メモリ: 7,716 KB
• スコア: 5,139,718,010
• 最終ジャッジ日時: 2025-07-26 16:54:01
• 合計ジャッジ時間: 105,620 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

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

ソースコード

#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <algorithm>
#include <chrono>
#include <random>
#include <cmath>
#include <cstdint>
#include <array>

using namespace std;

// --- 焼きなましパラメータ ---
const double TIME_LIMIT_MS = 1990.0;
const double SA_START_TEMP = 100000.0;
const double SA_END_TEMP = 3.0;
const double TWO_OPT_PROBABILITY = 0.1;
const int TIME_CHECK_INTERVAL = 250; 

// --- グローバル定数 (変更不要) ---
const int N_CONST = 10;
const int T_CONST = 1000;

// --- xoshiro256++ 高速乱数生成器 ---
// see: https://prng.di.unimi.it/
class Xoshiro256 {
public:
    using result_type = uint64_t;
    static constexpr result_type min() { return 0; }
    static constexpr result_type max() { return UINT64_MAX; }

    Xoshiro256() : Xoshiro256(chrono::steady_clock::now().time_since_epoch().count()) {}
    explicit Xoshiro256(uint64_t seed) {
        s[0] = split_mix64(seed);
        s[1] = split_mix64(seed);
        s[2] = split_mix64(seed);
        s[3] = split_mix64(seed);
    }

    result_type operator()() {
        const uint64_t result = rotl(s[0] + s[3], 23) + s[0];
        const uint64_t t = s[1] << 17;
        s[2] ^= s[0];
        s[3] ^= s[1];
        s[1] ^= s[2];
        s[0] ^= s[3];
        s[2] ^= t;
        s[3] = rotl(s[3], 45);
        return result;
    }

    inline uint64_t next_int(uint64_t upper_bound) {
        if (upper_bound == 0) return 0;
        return operator()() % upper_bound;
    }

    inline double next_double() {
        return (operator()() >> 11) * (1.0 / (1ULL << 53));
    }

private:
    array<uint64_t, 4> s;
    static inline uint64_t rotl(const uint64_t x, int k) {
        return (x << k) | (x >> (64 - k));
    }
    static uint64_t split_mix64(uint64_t& x) {
        x += 0x9e3779b97f4a7c15;
        uint64_t z = x;
        z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
        z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
        return z ^ (z >> 31);
    }
};

// グローバル乱数生成器
Xoshiro256 rng;

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

    State(const vector<vector<int>>& initial_grid) {
        r = 0; c = 0; s = 0;
        grid = initial_grid;
        ops_count = 0;
        ops_log.reserve(T_CONST + 50);
        score = 0;
        for(const auto& row : grid) {
            for(int cell_val : row) {
                score += cell_val;
            }
        }
    }

    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') {
            long long old_val = grid[r][c];
            grid[r][c] ^= s;
            score += (long long)grid[r][c] - old_val;
        }
        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);
        }
    }
};

// --- ヘルパー関数 ---
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 特定のターゲット(tr, tc)への最適な操作列を見つける（序盤・中盤用）
 */
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 total_ops = "";
    long long total_increase = 0;

    int temp_s = current_state.s;
    vector<vector<int>> temp_grid = current_state.grid;
    int temp_r = current_state.r;
    int temp_c = current_state.c;

    for (char op : move_ops) {
        if (current_state.ops_count + total_ops.length() >= T_CONST) break;
        
        total_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_w_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_w_increase > 0 && current_state.ops_count + total_ops.length() + 1 + dist_to_target <= T_CONST) {
            total_ops += 'W';
            total_increase += potential_w_increase;
            temp_grid[temp_r][temp_c] ^= temp_s;
        }

        if (current_state.ops_count + total_ops.length() < T_CONST) {
            int s_after_copy = temp_s ^ temp_grid[temp_r][temp_c];
            int target_value = temp_grid[tr][tc];

            long long score_at_target_if_no_copy = (long long)(target_value ^ temp_s);
            long long score_at_target_if_copy = (long long)(target_value ^ s_after_copy);

            if (score_at_target_if_copy > score_at_target_if_no_copy) {
                total_ops += 'C';
                temp_s = s_after_copy;
            }
        }
    }
    
    if (current_state.ops_count + total_ops.length() < T_CONST) {
        long long final_increase = (long long)(temp_grid[tr][tc] ^ temp_s) - temp_grid[tr][tc];
        if (final_increase > 0) {
            total_ops += 'W';
            total_increase += final_increase;
        }
    }
    return {total_ops, total_increase};
}

// ★★★ 変更点 (ここから) ★★★

/**
 * @brief 指定された経路を通った場合の最適な操作列とスコア上昇量を計算する
 * @param current_state 現在の状態
 * @param move_ops 試行する移動経路の文字列 (例: "DDRR")
 * @param tr 最終的な目的地の行
 * @param tc 最終的な目的地の列
 * @return pair<string, long long> {最適な操作列, スコア上昇量}
 */
pair<string, long long> find_best_ops_for_path(const State& current_state, const string& move_ops, int tr, int tc) {
    string total_ops = "";
    long long total_increase = 0;

    int temp_s = current_state.s;
    vector<vector<int>> temp_grid = current_state.grid;
    int temp_r = current_state.r;
    int temp_c = current_state.c;

    for (char op : move_ops) {
        if (current_state.ops_count + total_ops.length() >= T_CONST) break;
        
        total_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_w_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_w_increase > 0 && current_state.ops_count + total_ops.length() + 1 + dist_to_target <= T_CONST) {
            total_ops += 'W';
            total_increase += potential_w_increase;
            temp_grid[temp_r][temp_c] ^= temp_s;
        }

        if (current_state.ops_count + total_ops.length() < T_CONST) {
            int s_after_copy = temp_s ^ temp_grid[temp_r][temp_c];
            long long score_at_target_if_no_copy = (long long)(current_state.grid[tr][tc] ^ temp_s);
            long long score_at_target_if_copy = (long long)(current_state.grid[tr][tc] ^ s_after_copy);

            if (score_at_target_if_copy > score_at_target_if_no_copy) {
                total_ops += 'C';
                temp_s = s_after_copy;
            }
        }
    }
    
    if (current_state.ops_count + total_ops.length() < T_CONST) {
        long long final_increase = (long long)(temp_grid[tr][tc] ^ temp_s) - temp_grid[tr][tc];
        if (final_increase > 0) {
            total_ops += 'W';
            total_increase += final_increase;
        }
    }
    
    return {total_ops, total_increase};
}

/**
 * @brief スタートからゴールまでの2つの候補経路（縦→横、横→縦）を生成する
 * @param r1, c1 スタート地点
 * @param r2, c2 ゴール地点
 * @return vector<string> 経路文字列のベクター
 */
vector<string> generate_candidate_paths(int r1, int c1, int r2, int c2) {
    vector<string> paths;
    paths.reserve(2);

    string vert_moves = string(abs(r1 - r2), (r1 < r2) ? 'D' : 'U');
    string horz_moves = string(abs(c1 - c2), (c1 < c2) ? 'R' : 'L');

    // 経路1: 縦 -> 横
    paths.push_back(vert_moves + horz_moves);

    // 経路2: 横 -> 縦 (経路1と異なる場合のみ追加)
    if (!vert_moves.empty() && !horz_moves.empty()) {
        paths.push_back(horz_moves + vert_moves);
    }
    
    return paths;
}

// ★★★ 変更点 (ここまで) ★★★


/**
 * @brief 指定された訪問順で完全なシミュレーションを実行し、最終状態を返す
 */
State run_simulation(const vector<pair<int, int>>& visit_order, const vector<vector<int>>& initial_grid) {
    State current_state(initial_grid);
    
    // 序盤・中盤フェーズ: 貪欲にターゲットを巡る
    for(const auto& target_pos : visit_order) {
        if (current_state.ops_count >= T_CONST) break;
        auto result = find_best_ops_for_target(current_state, target_pos.first, target_pos.second);
        current_state.apply_ops_string(result.first);
    }

    // ★★★ 後半戦略 (改善版) ★★★
    while (true) {
        int remaining_ops = T_CONST - current_state.ops_count;
        if (remaining_ops < 2) break;

        int best_target_r = -1, best_target_c = -1;
        double max_gain_per_op = 0.0;

        // 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 + 1 > remaining_ops) continue;

                long long gain = (long long)(current_state.grid[r][c] ^ current_state.s) - current_state.grid[r][c];
                if (gain <= 0) continue;

                double gain_per_op = (double)gain / (dist + 1.0);
                if (gain_per_op > max_gain_per_op) {
                    max_gain_per_op = gain_per_op;
                    best_target_r = r;
                    best_target_c = c;
                }
            }
        }

        if (best_target_r == -1) break; // 利益の出るターゲットが見つからない

        // 2. そのターゲットへの2通りの経路（縦→横、横→縦）を試し、最善手を探す
        vector<string> candidate_paths = generate_candidate_paths(current_state.r, current_state.c, best_target_r, best_target_c);

        string best_overall_ops = "";
        long long max_overall_gain = -1;

        for (const auto& path : candidate_paths) {
            pair<string, long long> result = find_best_ops_for_path(current_state, path, best_target_r, best_target_c);
            
            if (result.second > max_overall_gain) {
                if (current_state.ops_count + result.first.length() <= T_CONST) {
                    max_overall_gain = result.second;
                    best_overall_ops = result.first;
                }
            }
        }

        // 3. 見つかった最善手があれば適用する
        if (max_overall_gain > 0) {
            current_state.apply_ops_string(best_overall_ops);
        } else {
            break; // どの経路でも利益が出なければ終了
        }
    }
    return current_state;
}


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];
        }
    }

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

    vector<pair<int, int>> current_order = base_order;
    
    State best_state = run_simulation(current_order, initial_grid);
    long long best_score = best_state.score;
    long long current_score = best_score;

    int iteration = 0;
    int accepted_count = 0;

    cerr << "[SA] Initial Score: " << best_score << endl;

    // --- 改善された焼きなましループ ---
    double elapsed_ms = 0;
    while(true) {
        iteration++;
        
        // ★★★ 毎回、時間を確認 ★★★
        auto current_time_point = chrono::steady_clock::now();
        elapsed_ms = chrono::duration_cast<chrono::milliseconds>(current_time_point - start_time).count();
        if (elapsed_ms >= TIME_LIMIT_MS) {
            break;
        }

        vector<pair<int, int>> new_order = current_order;
        if (rng.next_double() < TWO_OPT_PROBABILITY) {
            int i = rng.next_int(new_order.size());
            int j = rng.next_int(new_order.size());
            if (i == j) continue;
            if (i > j) swap(i, j);
            reverse(new_order.begin() + i, new_order.begin() + j);
        } else {
            int i = rng.next_int(new_order.size());
            int j = rng.next_int(new_order.size());
            if (i == j) continue;
            swap(new_order[i], new_order[j]);
        }
        
        State new_state = run_simulation(new_order, initial_grid);
        long long new_score = new_state.score;
        
        double temp = SA_START_TEMP + (SA_END_TEMP - SA_START_TEMP) * elapsed_ms / TIME_LIMIT_MS;
        double delta = (double)new_score - current_score;

        if (delta > 0 || (temp > 0 && rng.next_double() < exp(delta / temp))) {
            current_order = move(new_order);
            current_score = new_score;
            accepted_count++;
            if (current_score > best_score) {
                best_score = current_score;
                best_state = move(new_state);
            }
        }

        if (iteration % TIME_CHECK_INTERVAL == 0) {
            cerr << "[SA] iter:" << iteration << " time:" << (int)elapsed_ms << "ms"
                 << " temp:" << (int)temp << " score:" << current_score 
                 << " best:" << best_score << " accept_rate:" << (iteration > 0 ? (double)accepted_count/iteration : 0.0) << endl;
        }
    }

    for (char op : best_state.ops_log) {
        cout << op << "\n";
    }

    cerr << "--- Final Debug Info ---" << endl;
    cerr << "SA iterations: " << iteration << endl;
    cerr << "Best score found: " << best_score << endl;
    cerr << "Final operations count: " << best_state.ops_log.length() << "/" << T_CONST << endl;
    
    State final_check_state(initial_grid);
    final_check_state.apply_ops_string(best_state.ops_log);
    cerr << "Score from final output (re-calculated): " << final_check_state.score << endl;

    return 0;
}