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

• 問題: No.5022 XOR Printer
• ユーザー: ymym_tymblack
• 提出日時: 2025-07-26 16:18:24
• 言語: C++23 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 1,807 ms / 2,000 ms
• コード長: 10,865 bytes
• コンパイル時間: 5,226 ms
• コンパイル使用メモリ: 325,984 KB
• 実行使用メモリ: 7,716 KB
• スコア: 4,411,356,137
• 最終ジャッジ日時: 2025-07-26 16:20:05
• 合計ジャッジ時間: 99,287 ms
• ジャッジサーバーID （参考情報）: judge2 / judge6

ファイルパターン	結果
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;
}

// 任意の状態から貪欲に hand_count 手の手列を生成 (盤面と状態を更新)
vector<string> greedy_from_state(vector<vector<int>>& board, int& cx, int& cy, int& cs, int hand_count, mt19937& rng) {
    vector<string> seq;
    seq.reserve(hand_count);
    uniform_int_distribution<int> uni_dir(0, 5);
    for (int step = 0; step < hand_count; ++step) {
        long long best_score = LLONG_MIN;
        string best_cmd = command_list[uni_dir(rng)]; // fallback
        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;
            int nx = cx, ny = cy, ns = cs;
            vector<vector<int>> tmp = board;
            process_command(tmp, nx, ny, ns, cmd);
            long long sc = calc_score(tmp);
            if (sc > best_score) {
                best_score = sc;
                best_cmd = cmd;
            }
        }
        if (best_score <= base_score) {
            // たまにランダムで揺らす
            best_cmd = command_list[uni_dir(rng)];
            while ((best_cmd == "U" || best_cmd == "D" || best_cmd == "L" || best_cmd == "R") && !can_move(cx, cy, best_cmd)) {
                best_cmd = command_list[uni_dir(rng)];
            }
        }
        process_command(board, cx, cy, cs, best_cmd);
        seq.push_back(best_cmd);
    }
    return seq;
}

// ビームサーチで hand_count 手の手列を構築
vector<string> beam_search_from_state(const vector<vector<int>>& init_board, int x0, int y0, int s0, int hand_count, int beam_width = 200) {
    struct Node {
        vector<vector<int>> board;
        int x, y, s;
        long long score;
        vector<string> path;
        bool operator<(const Node& other) const { // for priority_queue (min-heap)
            return score > other.score; // 逆順（高スコア優先）
        }
    };

    vector<Node> beam;
    beam.reserve(beam_width);
    beam.push_back({init_board, x0, y0, s0, calc_score(init_board), {}});

    for (int depth = 0; depth < hand_count; ++depth) {
        vector<Node> cand;
        cand.reserve(beam.size() * 6);
        for (const Node& node : beam) {
            for (const string& cmd : command_list) {
                if ((cmd == "U" || cmd == "D" || cmd == "L" || cmd == "R") && !can_move(node.x, node.y, cmd)) continue;
                Node nxt = node; // コピー
                nxt.path.push_back(cmd);
                process_command(nxt.board, nxt.x, nxt.y, nxt.s, cmd);
                nxt.score = calc_score(nxt.board);
                cand.push_back(move(nxt));
            }
        }
        // 上位 beam_width を残す
        nth_element(cand.begin(), cand.begin() + min(beam_width, (int)cand.size()) - 1, cand.end());
        cand.resize(min(beam_width, (int)cand.size()));
        beam.swap(cand);
    }

    // 最良ノードを取得
    Node* best = &beam[0];
    for (Node& n : beam) if (n.score > best->score) best = &n;
    return best->path;
}

// 焼きなましで手列を改善
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;

        vector<string> new_seq = seq;
        long long new_score;

        // --- 大規模再構築 or 小規模変形を選択 ---
        if (rng() % 10 == 0) { // 10% で大規模再構築
            uniform_int_distribution<int> pos_dist(0, T - 2);
            int l = pos_dist(rng);
            int len = min(T - l, (int)(T / 5)); // 全体の 20% 程度を再構築

            // l までシミュレートして状態取得
            vector<vector<int>> board = initial_board;
            int cx = 0, cy = 0, cs = 0;
            for (int i = 0; i < l; ++i) {
                if (!can_move(cx, cy, seq[i]) && (seq[i] == "U" || seq[i] == "D" || seq[i] == "L" || seq[i] == "R")) {
                    // 現在の手列がそもそも無効なら break
                    board.clear();
                    break;
                }
                process_command(board, cx, cy, cs, seq[i]);
            }
            if (!board.empty()) {
                // 再構築部分を greedy で生成
                vector<string> rebuilt = greedy_from_state(board, cx, cy, cs, len, rng);
                for (int i = 0; i < len; ++i) new_seq[l + i] = rebuilt[i];
            }
        } else {
            // 小規模（従来）のランダム区間書き換え
            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));
            uniform_int_distribution<int> cmd_dist_local(0, (int)command_list.size() - 1);
            for (int i = l; i < l + len; ++i) {
                new_seq[i] = command_list[cmd_dist_local(rng)];
            }
        }

        if (!simulate(new_seq, new_score)) continue;

        long long delta = new_score - best_score;
        if (delta > 0 || exp((double)delta / temperature) > (double)rng() / rng.max()) {
            seq.swap(new_seq);
            best_score = new_score;
            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;
}