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

• 問題: No.5022 XOR Printer
• ユーザー: yimiya（いみや）
• 提出日時: 2025-07-26 15:04:22
• 言語: C++23 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 2 ms / 2,000 ms
• コード長: 4,348 bytes
• コンパイル時間: 3,473 ms
• コンパイル使用メモリ: 293,892 KB
• 実行使用メモリ: 7,720 KB
• スコア: 4,832,797,499
• 最終ジャッジ日時: 2025-07-26 15:04:29
• 合計ジャッジ時間: 5,295 ms
• ジャッジサーバーID （参考情報）: judge3 / judge5

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

ソースコード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll MAX_OP = 1000;
ll N, T;
vector<vector<ll>> grid;
ll cnt = 0;
ll x = 0, y = 0;
ll s = 0;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

// 移動候補（上下左右）
vector<pair<int,int>> moves = {{1,0},{-1,0},{0,1},{0,-1}};

// 1マス移動出力
bool moveStep(int nx, int ny) {
    if (nx < 0 || ny < 0 || nx >= N || ny >= N) return false;
    if (cnt >= MAX_OP) return false;

    if (nx == x + 1 && ny == y) cout << "R\n";
    else if (nx == x - 1 && ny == y) cout << "L\n";
    else if (nx == x && ny == y + 1) cout << "D\n";
    else if (nx == x && ny == y - 1) cout << "U\n";
    else return false;

    x = nx; y = ny;
    cnt++;
    return true;
}

bool copyOp() {
    if (cnt >= MAX_OP) return false;
    s ^= grid[y][x];
    cout << "C\n";
    cnt++;
    return true;
}

bool writeOp() {
    if (cnt >= MAX_OP) return false;
    ll oldv = grid[y][x];
    ll newv = oldv ^ s;
    if (newv > oldv) {
        grid[y][x] = newv;
        cout << "W\n";
        cnt++;
        return true;
    }
    return false;
}

ll calcScore() {
    ll sum = 0;
    for (auto &row : grid)
        for (auto &v : row) sum += v;
    return sum;
}

// 書き込み候補を更新
vector<pair<int,int>> candidates;
void updateCandidates() {
    candidates.clear();
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            ll oldv = grid[i][j];
            ll newv = oldv ^ s;
            if(newv > oldv) candidates.emplace_back(j,i);
        }
    }
}

// 現在地から最も近い候補セルを探す
bool findNearestCandidate(int &nx, int &ny) {
    if(candidates.empty()) return false;
    int best_idx = -1;
    int best_dist = INT_MAX;
    for(int i=0;i<(int)candidates.size();i++){
        int cx = candidates[i].first;
        int cy = candidates[i].second;
        int dist = abs(cx - x) + abs(cy - y);
        if(dist < best_dist){
            best_dist = dist;
            best_idx = i;
        }
    }
    if(best_idx == -1) return false;
    nx = candidates[best_idx].first;
    ny = candidates[best_idx].second;
    return true;
}

// 現在位置から1マスだけ候補に近づく
bool moveTowards(int tx, int ty){
    if(x < tx) return moveStep(x+1, y);
    if(x > tx) return moveStep(x-1, y);
    if(y < ty) return moveStep(x, y+1);
    if(y > ty) return moveStep(x, y-1);
    return false; // もうそこにいる
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> T;
    grid.resize(N, vector<ll>(N));
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            cin >> grid[i][j];

    ll curScore = calcScore();
    const double T0 = 2500.0;

    while (cnt < MAX_OP) {
        double temperature = T0 * (1.0 - double(cnt) / MAX_OP);
        if (temperature < 1e-4) break;

        // 書き込み候補を更新
        updateCandidates();

        // 適度にコピーを挟む（10%の確率）
        if(rng() % 10 == 0) {
            copyOp();
            continue;
        }

        int nx, ny;
        if(findNearestCandidate(nx, ny)) {
            // 候補セルに1マス近づく
            if(moveTowards(nx, ny)) continue;

            // 到達してたら書き込み判定
            ll oldv = grid[y][x];
            ll newv = oldv ^ s;
            if(newv > oldv){
                ll delta = newv - oldv;
                if(delta >= 0){
                    writeOp();
                    curScore += delta;
                } else {
                    double prob = exp(delta / temperature);
                    if(uniform_real_distribution<double>(0,1)(rng) < prob){
                        writeOp();
                        curScore += delta;
                    }
                }
                continue;
            }
        }

        // 書き込み候補がなければランダムに1マス移動
        vector<pair<int,int>> candMoves;
        for(auto &m : moves){
            int mx = x + m.first;
            int my = y + m.second;
            if(mx>=0 && mx<N && my>=0 && my<N) candMoves.emplace_back(mx,my);
        }
        if(!candMoves.empty()){
            auto [mx, my] = candMoves[uniform_int_distribution<int>(0, (int)candMoves.size()-1)(rng)];
            moveStep(mx, my);
        }
    }

    return 0;
}