結果

問題 No.5022 XOR Printer
コンテスト
ユーザー yimiya（いみや）
提出日時 2025-07-26 15:19:47
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 4 ms / 2,000 ms
コード長 4,793 bytes
コンパイル時間 3,434 ms
コンパイル使用メモリ 303,356 KB
実行使用メモリ 7,716 KB
スコア 4,813,057,228
最終ジャッジ日時 2025-07-26 15:19:53
合計ジャッジ時間 5,398 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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}};
vector<vector<int>> visit_count;

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++;
    visit_count[y][x]++;
    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;
    double best_score = 1e18;
    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);
        double score = dist * (1.0 + 1.0 / (1 + visit_count[cy][cx]));
        if(score < best_score){
            best_score = score;
            best_idx = i;
        }
    }
    if(best_idx == -1) return false;
    nx = candidates[best_idx].first;
    ny = candidates[best_idx].second;
    return true;
}

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

pair<int,int> weightedRandomMove(const vector<pair<int,int>>& candMoves) {
    vector<double> weights;
    for(auto& p : candMoves){
        int vx = p.first;
        int vy = p.second;
        double w = 1.0 / (1 + visit_count[vy][vx]);
        weights.push_back(w);
    }
    discrete_distribution<int> dist(weights.begin(), weights.end());
    int idx = dist(rng);
    return candMoves[idx];
}

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

    visit_count.assign(N, vector<int>(N, 0));
    visit_count[y][x] = 1;

    ll curScore = calcScore();

    // 二段階温度設定
    const double T1 = 10000.0;  // 高温フェーズ
    const double T2 = 100.0;    // 低温フェーズ

    while (cnt < MAX_OP) {
        double temperature;
        if(cnt < 700){
            temperature = T1 * (1.0 - double(cnt) / (MAX_OP/2));
        } else {
            temperature = T2 * (1.0 - double(cnt - MAX_OP/2) / (MAX_OP/2));
        }
        if (temperature < 1e-6) temperature = 1e-6;

        updateCandidates();

        // ランダムに s を更新（確率10%）
        if (rng() % 15 == 0) {
            copyOp();
            continue;
        }

        int nx, ny;
        if(findNearestCandidate(nx, ny)) {
            if(moveTowards(nx, ny)) continue;

            // 到達してたら書き込み判定
            ll oldv = grid[y][x];
            ll newv = oldv ^ s;
            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;
        }

        // 候補がなければ訪問回数重み付きのランダム移動
        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] = weightedRandomMove(candMoves);
            moveStep(mx, my);
        }
    }

    return 0;
}
0