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

• 問題: No.5022 XOR Printer
• ユーザー: ymym_tymblack
• 提出日時: 2025-07-26 15:33:52
• 言語: C++23 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 1,805 ms / 2,000 ms
• コード長: 6,633 bytes
• コンパイル時間: 3,779 ms
• コンパイル使用メモリ: 306,496 KB
• 実行使用メモリ: 7,720 KB
• スコア: 4,409,129,460
• 最終ジャッジ日時: 2025-07-26 15:35:31
• 合計ジャッジ時間: 98,187 ms
• ジャッジサーバーID （参考情報）: judge3 / judge1

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

ソースコード

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#define all(x) (x).begin(),(x).end()
typedef long long ll;
const long long INF = 1LL << 60; // 十分大きな値 (ここでは 2^60 とする)
#include <algorithm>
#include <cctype>
#include <cstddef>
#include <iostream>
#include <iterator>
#include <string_view>
#include <type_traits>

template<class T> void chmin(T& a, T b) {
    if (a > b) {
        a = b;
    }
}

template<class T> void chmax(T& a, T b) {
    if (a < b) {
        a = b;
    }
}

#ifdef LOCAL
#  include <debug_print.hpp>
#  define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)
#else
#  define debug(...) (static_cast<void>(0))
#endif

int N, T;
vector<vector<int>> A;
int x = 0, y = 0, s = 0;
vector<string> command_list = {"U", "D", "L", "R", "W", "C"};

// 移動可能かどうかを判定
bool can_move(int x, int y, const string& command) {
    if (command == "U") {
        return x > 0;
    } else if (command == "D") {
        return x < N - 1;
    } else if (command == "L") {
        return y > 0;
    } else if (command == "R") {
        return y < N - 1;
    }
    return true;
}

// コマンドを実行
void process_command(vector<vector<int>>& board, int& x, int& y, int& s, const string& command) {
    if (command == "U") {
        x = x - 1;
    } else if (command == "D") {
        x = x + 1;
    } else if (command == "L") {
        y = y - 1;
    } else if (command == "R") {
        y = y + 1;
    } else if (command == "W") {
        board[x][y] ^= s;
    } else if (command == "C") {
        s ^= board[x][y];
    }
}

// スコアを計算
int calc_score(const vector<vector<int>>& board) {
    int score = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            score += board[i][j];
        }
    }
    return score;
}

// 盤面の初期値を保持（焼きなまし時のリセット用）
vector<vector<int>> initial_board;

// 時間計測用
inline long long now() {
    return chrono::duration_cast<chrono::milliseconds>(
               chrono::steady_clock::now().time_since_epoch())
        .count();
}

// 与えられた手列をシミュレートし，スコアを返す。
// 無効な手列なら false を返す。
bool simulate(const vector<string>& seq, long long& score_out) {
    vector<vector<int>> board = initial_board; // コピー
    int tx = 0, ty = 0, ts = 0;
    for (const string& cmd : seq) {
        if ((cmd == "U" || cmd == "D" || cmd == "L" || cmd == "R") &&
            !can_move(tx, ty, cmd)) {
            return false; // 壁に衝突
        }
        process_command(board, tx, ty, ts, cmd);
    }
    score_out = calc_score(board);
    return true;
}

// Greedy で初期手列を構築
vector<string> build_greedy_sequence(int T) {
    vector<string> seq;
    seq.reserve(T);

    vector<vector<int>> board = initial_board;
    int cx = 0, cy = 0, cs = 0;

    random_device rd;
    mt19937 rng(rd());

    for (int step = 0; step < T; ++step) {
        long long best_score = LLONG_MIN;
        string best_cmd = "W";
        // 現在の盤面得点
        long long base_score = calc_score(board);

        // 試せるコマンドを列挙
        for (const string& cmd : command_list) {
            if ((cmd == "U" || cmd == "D" || cmd == "L" || cmd == "R") &&
                !can_move(cx, cy, cmd))
                continue;
            // 状態をコピーして 1 手だけ適用
            int nx = cx, ny = cy, ns = cs;
            vector<vector<int>> tmp_board = board;
            process_command(tmp_board, nx, ny, ns, cmd);
            long long sc = calc_score(tmp_board);
            if (sc > best_score) {
                best_score = sc;
                best_cmd = cmd;
            }
        }

        // すべての cmd が同点（動かすだけ）ならランダムで選ぶ
        if (best_score <= base_score) {
            // ランダムで動ける方向または C を選択
            vector<string> cand;
            for (const string& cmd : command_list) {
                if ((cmd == "U" || cmd == "D" || cmd == "L" || cmd == "R")) {
                    if (can_move(cx, cy, cmd)) cand.push_back(cmd);
                } else {
                    cand.push_back(cmd); // W or C
                }
            }
            uniform_int_distribution<int> uni(0, (int)cand.size() - 1);
            best_cmd = cand[uni(rng)];
        }

        // best_cmd を実際に適用
        process_command(board, cx, cy, cs, best_cmd);
        seq.push_back(best_cmd);
    }
    return seq;
}

// 焼きなましで手列を改善
vector<string> simulated_annealing(vector<string> seq, long long best_score, long long time_limit_ms = 1800) {
    const long long start_time = now();
    const double T0 = 2000.0;
    const double T_end = 1e-3;

    random_device rd;
    mt19937 rng(rd());
    uniform_int_distribution<int> cmd_dist(0, (int)command_list.size() - 1);

    vector<string> best_seq = seq;

    long long iter = 0;
    while (now() - start_time < time_limit_ms) {
        ++iter;
        double progress = (double)(now() - start_time) / (double)time_limit_ms;
        double temperature = pow(T_end / T0, progress) * T0;

        // ランダム区間を書き換え (長さ 1～10)
        uniform_int_distribution<int> pos_dist(0, T - 1);
        int l = pos_dist(rng);
        int len = min(T - l, (int)(pos_dist(rng) % 10 + 1));

        vector<string> new_seq = seq;
        for (int i = l; i < l + len; ++i) {
            new_seq[i] = command_list[cmd_dist(rng)];
        }

        long long new_score;
        if (!simulate(new_seq, new_score)) continue; // 無効手列

        long long delta = new_score - best_score;
        if (delta > 0 || exp(delta / temperature) > (double)rng() / rng.max()) {
            // 受理
            seq.swap(new_seq);
            best_score = new_score;
            if (best_score > calc_score(initial_board)) {
                best_seq = seq;
            }
        }
    }
    return best_seq;
}

int main() {
    // 入力
    cin >> N >> T;
    A.resize(N, vector<int>(N));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> A[i][j];
        }
    }

    // 初期盤面を保存
    initial_board = A;

    // Greedy で初期手列を生成
    vector<string> seq = build_greedy_sequence(T);
    long long best_score;
    simulate(seq, best_score);

    // 焼きなましで改善
    seq = simulated_annealing(seq, best_score);

    // 出力
    for (const string& cmd : seq) {
        cout << cmd << '\n';
    }

    return 0;
}