結果

問題 No.5022 XOR Printer
ユーザー yimiya（いみや）
提出日時 2025-07-26 16:01:20
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 5,133 bytes
コンパイル時間 3,831 ms
コンパイル使用メモリ 302,740 KB
実行使用メモリ 7,716 KB
スコア 4,861,369,354
最終ジャッジ日時 2025-07-26 16:01:27
合計ジャッジ時間 5,904 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge6
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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(1);
vector<pair<int,int>> moves = {{1,0},{-1,0},{0,1},{0,-1}};
vector<vector<int>> visit_count;

pair<int, int> last_copy_pos = {-1, -1}; // 最後にC操作した位置

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;
    if (last_copy_pos.first == x && last_copy_pos.second == y) return false;

    s ^= grid[y][x];
    cout << "C\n";
    cnt++;
    last_copy_pos = {x, y};
    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) {
    ll max_cell_value = 1;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            max_cell_value = max(max_cell_value, grid[i][j]);
        }
    }

    const double alpha = 100000.0;
    vector<double> weights;
    for(auto& p : candMoves){
        int vx = p.first;
        int vy = p.second;
        double visit_w = 1.0 / (1 + visit_count[vy][vx]);
        double score_w = 1.0 + alpha * double(max_cell_value - grid[vy][vx]) / max_cell_value;
        weights.push_back(visit_w * score_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 = 100000000.0;
    const double T2 = 10000.0;

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

        updateCandidates();

        if(cnt < 1000){
            if (rng() % 4 == 0) {
                if (copyOp()) continue;
            }
        } else {
            if (rng() % 10 == 0) {
                if (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