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

• 問題: No.5022 XOR Printer
• ユーザー: yimiya（いみや）
• 提出日時: 2025-07-26 16:16:37
• 言語: C++23 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 1,983 ms / 2,000 ms
• コード長: 5,506 bytes
• コンパイル時間: 3,849 ms
• コンパイル使用メモリ: 310,348 KB
• 実行使用メモリ: 7,716 KB
• スコア: 5,048,659,411
• 最終ジャッジ日時: 2025-07-26 16:18:26
• 合計ジャッジ時間: 107,266 ms
• ジャッジサーバーID （参考情報）: judge6 / judge2

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

ソースコード

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

const int MAX_OP = 1000;
const double TL = 1.98; // seconds
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int N, T;
Grid original_grid;

vector<pair<int, int>> directions = {{1,0},{-1,0},{0,1},{0,-1}};

struct Result {
    ll score;
    vector<string> log;
};

Result run_once(const Grid& base_grid) {
    Grid grid = base_grid;
    vector<vector<int>> visit_count(N, vector<int>(N, 0));
    vector<string> log;

    int x = 0, y = 0;
    ll s = 0;
    int cnt = 0;
    pair<int,int> last_copy_pos = {-1, -1};

    auto moveStep = [&](int nx, int ny) -> bool {
        if (nx < 0 || ny < 0 || nx >= N || ny >= N || cnt >= MAX_OP) return false;
        if (nx == x+1 && ny == y) log.emplace_back("R");
        else if (nx == x-1 && ny == y) log.emplace_back("L");
        else if (nx == x && ny == y+1) log.emplace_back("D");
        else if (nx == x && ny == y-1) log.emplace_back("U");
        else return false;
        x = nx; y = ny; cnt++;
        visit_count[y][x]++;
        return true;
    };

    auto copyOp = [&]() -> bool {
        if (cnt >= MAX_OP) return false;
        if (last_copy_pos.first == x && last_copy_pos.second == y) return false;
        s ^= grid[y][x];
        log.emplace_back("C");
        cnt++;
        last_copy_pos = {x, y};
        return true;
    };

    auto writeOp = [&]() -> bool {
        if (cnt >= MAX_OP) return false;
        ll oldv = grid[y][x];
        ll newv = oldv ^ s;
        if (newv > oldv) {
            grid[y][x] = newv;
            log.emplace_back("W");
            cnt++;
            return true;
        }
        return false;
    };

    auto updateCandidates = [&]() {
        vector<pair<int,int>> cand;
        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) cand.emplace_back(j,i);
            }
        return cand;
    };

    auto findNearestCandidate = [&](const vector<pair<int,int>>& cand) {
        int best_idx = -1;
        double best_score = 1e18;
        for (int i = 0; i < (int)cand.size(); i++) {
            int cx = cand[i].first, cy = cand[i].second;
            int dist = abs(cx - x) + abs(cy - y);
            double score = dist * (1.0 + 1.0 / (1 + visit_count[cy][cx])) / (1.0 + grid[cy][cx]);
            if (score < best_score) {
                best_score = score;
                best_idx = i;
            }
        }
        return (best_idx == -1) ? pair<int,int>{-1,-1} : cand[best_idx];
    };

    auto 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 = 100.0;
        vector<double> weights;
        for(auto& p : candMoves){
            int vx = p.first, 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());
        return candMoves[dist(rng)];
    };

    const double T1 = 1e8, T2 = 1e4;
    while (cnt < MAX_OP) {
        double temperature = T1 * (1.0 - double(cnt) / MAX_OP);
        temperature = max(temperature, 1e-6);

        auto candidates = updateCandidates();
        if (rng()%4 == 0 && copyOp()) continue;

        auto target = findNearestCandidate(candidates);
        if (target.first != -1) {
            int tx = target.first, ty = target.second;
            if (x < tx) { if (moveStep(x+1, y)) continue; }
            if (x > tx) { if (moveStep(x-1, y)) continue; }
            if (y < ty) { if (moveStep(x, y+1)) continue; }
            if (y > ty) { if (moveStep(x, y-1)) continue; }
            ll oldv = grid[y][x], newv = oldv ^ s, delta = newv - oldv;
            if (delta >= 0 || exp(delta / temperature) > uniform_real_distribution<double>(0,1)(rng)) writeOp();
            continue;
        }

        vector<pair<int,int>> candMoves;
        for (auto& d : directions) {
            int mx = x + d.first, my = y + d.second;
            if (mx >= 0 && my >= 0 && mx < N && my < N)
                candMoves.emplace_back(mx, my);
        }
        if (!candMoves.empty()) {
            auto mv = weightedRandomMove(candMoves);
            moveStep(mv.first, mv.second);
        }
    }

    ll score = 0;
    for (auto& row : grid)
        for (auto v : row) score += v;
    return {score, log};
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> T;
    original_grid.resize(N, vector<ll>(N));
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            cin >> original_grid[i][j];

    auto start_time = chrono::high_resolution_clock::now();
    Result best_result = {0, {}};
    int iter = 0;

    while (true) {
        iter++;
        auto now = chrono::high_resolution_clock::now();
        double elapsed = chrono::duration<double>(now - start_time).count();
        if (elapsed > TL) break;

        Result res = run_once(original_grid);
        if (res.score > best_result.score) best_result = res;
    }

    for (auto& cmd : best_result.log) cout << cmd << "\n";
    return 0;
}