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

• 問題: No.5022 XOR Printer
• ユーザー: yimiya（いみや）
• 提出日時: 2025-07-26 18:09:40
• 言語: C++23 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 1,993 ms / 2,000 ms
• コード長: 5,920 bytes
• コンパイル時間: 3,398 ms
• コンパイル使用メモリ: 312,684 KB
• 実行使用メモリ: 7,720 KB
• スコア: 5,086,439,149
• 最終ジャッジ日時: 2025-07-26 18:11:29
• 合計ジャッジ時間: 106,761 ms
• ジャッジサーバーID （参考情報）: judge5 / judge2

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

ソースコード

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

const int MAX_OP = 1000;
const double TL = 1.990;
const int THREAD_NUM = thread::hardware_concurrency();
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}};
inline int IDX(int x, int y) { return y * N + x; }

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

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

    int x = 0, y = 0, cnt = 0;
    ll s = 0, max_cell_value = 1;
    pair<int,int> last_copy_pos = {-1, -1};
    bool candidate_dirty = true;
    vector<pair<int,int>> candidates;

    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[IDX(x,y)]++;
        return true;
    };

    auto copyOp = [&]() -> bool {
        if (cnt >= MAX_OP || (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};
        candidate_dirty = true;
        return true;
    };

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

    auto updateCandidates = [&]() {
        candidates.clear();
        for (int i = 0; i < N * N; ++i) {
            int j = i % N, k = i / N;
            if ((grid[k][j] ^ s) > grid[k][j]) candidates.emplace_back(j, k);
        }
        candidate_dirty = false;
    };

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

    auto weightedRandomMove = [&](const vector<pair<int,int>>& candMoves) {
        double alpha = 1e8, epsilon = 1e-9;
        vector<double> weights;
        for (auto& p : candMoves) {
            int vx = p.first, vy = p.second;
            double visit_w = 1.0 / (1 + visit_count[IDX(vx, vy)]);
            double score_w = 1.0 + alpha * double(max_cell_value - grid[vy][vx]) / (max_cell_value + epsilon);
            weights.push_back(visit_w * score_w);
        }
        discrete_distribution<int> dist(weights.begin(), weights.end());
        return candMoves[dist(local_rng)];
    };

    uniform_real_distribution<double> urd(0.0, 1.0);
    const double T1 = 1e10;

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

        if (candidate_dirty) updateCandidates();
        if ((local_rng() & 7) == 0 && copyOp()) continue;

        auto target = findNearestCandidate();
        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;
            if (newv - oldv >= 0 || exp((newv - oldv) / temperature) > urd(local_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 (int i = 0; i < N * N; ++i) score += grid[i / N][i % N];
    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];

    Result best_result = {0, {}};
    mutex mtx;

    auto start_time = chrono::high_resolution_clock::now();
    vector<thread> threads;

    for (int i = 0; i < THREAD_NUM; i++) {
        threads.emplace_back([&, i]() {
            mt19937 local_rng(rng()); // スレッドローカルな rng
            while (true) {
                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, local_rng);
                lock_guard<mutex> lock(mtx);
                if (res.score > best_result.score) best_result = res;
            }
        });
    }

    for (auto& th : threads) th.join();

    for (char c : best_result.log) cout << c << "\n";
    return 0;
}