結果

問題 No.5022 XOR Printer
ユーザー Ang1077
提出日時 2025-07-26 13:30:49
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 78 ms / 2,000 ms
コード長 5,513 bytes
コンパイル時間 3,434 ms
コンパイル使用メモリ 291,068 KB
実行使用メモリ 7,716 KB
スコア 4,435,690,771
最終ジャッジ日時 2025-07-26 13:30:59
合計ジャッジ時間 9,459 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

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

    int N, T;
    if (!(cin >> N >> T)) return 0;
    vector<vector<uint32_t>> A(N, vector<uint32_t>(N));
    for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) cin >> A[i][j];

    // 0-indexed state
    int r = 0, c = 0;
    uint32_t s = 0;
    vector<char> ops;

    auto move_to = [&](int tr, int tc) {
        while (r < tr) { ops.push_back('D'); ++r; }
        while (r > tr) { ops.push_back('U'); --r; }
        while (c < tc) { ops.push_back('R'); ++c; }
        while (c > tc) { ops.push_back('L'); --c; }
    };

    // Precompute all-pairs Manhattan distances on the grid (flattened indices 0..N*N-1)
    const int M = N * N;
    auto idx = [&](int rr, int cc){ return rr * N + cc; };
    vector<array<int,2>> rc(M);
    for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) rc[idx(i,j)] = {i,j};
    vector<vector<int>> dist(M, vector<int>(M, 0));
    for (int a = 0; a < M; ++a) {
        for (int b = 0; b < M; ++b) {
            dist[a][b] = abs(rc[a][0] - rc[b][0]) + abs(rc[a][1] - rc[b][1]);
        }
    }

    int used = 0;
    while (used < T) {
        int rem = T - used;
        // 全探索（0回コピー / 1回コピー / 2回コピー）
        long long best_delta = 0;
        int best_cost = 0;
        int cur = idx(r, c);

        // 計画の記録
        int plan_w = -1;
        int plan_p1 = -1;
        int plan_p2 = -1;
        int plan_k = 0; // コピー回数 0/1/2

        // 0C: そのままどこかに移動してW
        for (int w = 0; w < M; ++w) {
            int cost = dist[cur][w] + 1; // 移動 + W
            if (cost > rem) continue;
            auto [wr, wc] = rc[w];
            uint32_t new_val = (A[wr][wc] ^ s);
            long long delta = (long long)new_val - (long long)A[wr][wc];
            if (delta > best_delta) {
                best_delta = delta;
                best_cost = cost;
                plan_k = 0;
                plan_w = w;
                plan_p1 = plan_p2 = -1;
            }
        }

        // 1C: P1でCしてからW
        for (int p1 = 0; p1 < M; ++p1) {
            int cost_to_p1 = dist[cur][p1] + 1; // 移動 + C
            if (cost_to_p1 + 1 > rem) continue; // その後Wの1手が必要
            uint32_t s1 = s ^ A[ rc[p1][0] ][ rc[p1][1] ];
            for (int w = 0; w < M; ++w) {
                int cost = cost_to_p1 + dist[p1][w] + 1; // + 移動 + W
                if (cost > rem) continue;
                auto [wr, wc] = rc[w];
                uint32_t new_val = (A[wr][wc] ^ s1);
                long long delta = (long long)new_val - (long long)A[wr][wc];
                if (delta > best_delta) {
                    best_delta = delta;
                    best_cost = cost;
                    plan_k = 1;
                    plan_p1 = p1;
                    plan_w = w;
                    plan_p2 = -1;
                }
            }
        }

        // 2C: P1でC, P2でC, その後W
        // 残り手数が最低でも3（C,C,W）なければ不要
        if (rem >= 3) {
            for (int p1 = 0; p1 < M; ++p1) {
                int cost0 = dist[cur][p1] + 1; // 移動 + C
                if (cost0 + 2 > rem) continue; // 以後にC+Wが必要
                uint32_t s1 = s ^ A[ rc[p1][0] ][ rc[p1][1] ];
                for (int p2 = 0; p2 < M; ++p2) {
                    int cost1 = cost0 + dist[p1][p2] + 1; // 移動 + C
                    if (cost1 + 1 > rem) continue; // 以後にWが必要
                    uint32_t s2 = s1 ^ A[ rc[p2][0] ][ rc[p2][1] ];
                    for (int w = 0; w < M; ++w) {
                        int cost = cost1 + dist[p2][w] + 1; // 移動 + W
                        if (cost > rem) continue;
                        auto [wr, wc] = rc[w];
                        uint32_t new_val = (A[wr][wc] ^ s2);
                        long long delta = (long long)new_val - (long long)A[wr][wc];
                        if (delta > best_delta) {
                            best_delta = delta;
                            best_cost = cost;
                            plan_k = 2;
                            plan_p1 = p1;
                            plan_p2 = p2;
                            plan_w = w;
                        }
                    }
                }
            }
        }

        // 改善しない or 何も選べないなら終了
        if (best_delta <= 0 || plan_w < 0) break;

        // 実行
        if (plan_k == 0) {
            auto [wr, wc] = rc[plan_w];
            move_to(wr, wc);
            ops.push_back('W');
            A[wr][wc] ^= s;
        } else if (plan_k == 1) {
            auto [p1r, p1c] = rc[plan_p1];
            move_to(p1r, p1c);
            ops.push_back('C');
            s ^= A[p1r][p1c];
            auto [wr, wc] = rc[plan_w];
            move_to(wr, wc);
            ops.push_back('W');
            A[wr][wc] ^= s;
        } else {
            auto [p1r, p1c] = rc[plan_p1];
            move_to(p1r, p1c);
            ops.push_back('C');
            s ^= A[p1r][p1c];
            auto [p2r, p2c] = rc[plan_p2];
            move_to(p2r, p2c);
            ops.push_back('C');
            s ^= A[p2r][p2c];
            auto [wr, wc] = rc[plan_w];
            move_to(wr, wc);
            ops.push_back('W');
            A[wr][wc] ^= s;
        }

        used += best_cost;
    }

    for (char ch : ops) cout << ch << '\n';
    return 0;
}
0