結果

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

ソースコード

diff #
raw source code 

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

    // 状態
    int r = 0, c = 0;          // 現在位置 (0-indexed; 問題は(1,1)始点)
    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; }
    };
    auto manhattan = [&](int r1, int c1, int r2, int c2) {
        return abs(r1 - r2) + abs(c1 - c2);
    };

    int used = 0;
    while (used < T) {
        int rem = T - used;
        if (rem < 1) break;

        long long best_delta = 0; // 改善のみ採用
        int best_cost = 0;

        // 0/1/2回コピー用にベスト手を記憶
        int mode = -1;                   // 0,1,2
        int bwr = -1, bwc = -1;          // 書き込み先
        int bpr1 = -1, bpc1 = -1;        // 1回目コピー
        int bpr2 = -1, bpc2 = -1;        // 2回目コピー

        // --- コピー0回 ---
        // 現在位置→W、W(1手)
        for (int wr = 0; wr < N; ++wr) {
            for (int wc = 0; wc < N; ++wc) {
                int total_cost = manhattan(r, c, wr, wc) + 1; // move + W
                if (total_cost > rem) continue;
                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 = total_cost;
                    mode = 0;
                    bwr = wr; bwc = wc;
                }
            }
        }

        // --- コピー1回 ---
        for (int pr = 0; pr < N; ++pr) {
            for (int pc = 0; pc < N; ++pc) {
                int cost_to_p = manhattan(r, c, pr, pc);
                if (cost_to_p + 1 >= rem) continue; // その後Wまで行けない
                uint32_t s2 = s ^ A[pr][pc];
                for (int wr = 0; wr < N; ++wr) {
                    for (int wc = 0; wc < N; ++wc) {
                        int total_cost = cost_to_p + 1 + manhattan(pr, pc, wr, wc) + 1; // move + C + move + W
                        if (total_cost > rem) continue;
                        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 = total_cost;
                            mode = 1;
                            bpr1 = pr; bpc1 = pc;
                            bwr = wr;  bwc = wc;
                        }
                    }
                }
            }
        }

        // --- コピー2回 ---
        for (int p1r = 0; p1r < N; ++p1r) {
            for (int p1c = 0; p1c < N; ++p1c) {
                int d0 = manhattan(r, c, p1r, p1c);
                if (d0 + 2 >= rem) continue; // C,C,Wが必要なので最低+2、さらにWまでの移動が必要
                for (int p2r = 0; p2r < N; ++p2r) {
                    for (int p2c = 0; p2c < N; ++p2c) {
                        int d1 = manhattan(p1r, p1c, p2r, p2c);
                        // ここまでで d0 + 1(C) + d1 + 1(C) を消費、Wまでの移動とW(1)が必要
                        int base_cost = d0 + 1 + d1 + 1;
                        if (base_cost + 1 > rem) continue; // Wの1手分すら残らない
                        uint32_t s2 = s ^ A[p1r][p1c] ^ A[p2r][p2c];
                        for (int wr = 0; wr < N; ++wr) {
                            for (int wc = 0; wc < N; ++wc) {
                                int total_cost = base_cost + manhattan(p2r, p2c, wr, wc) + 1; // ... + move + W
                                if (total_cost > rem) continue;
                                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 = total_cost;
                                    mode = 2;
                                    bpr1 = p1r; bpc1 = p1c;
                                    bpr2 = p2r; bpc2 = p2c;
                                    bwr  = wr;  bwc  = wc;
                                }
                            }
                        }
                    }
                }
            }
        }

        // 改善なしなら終了
        if (best_delta <= 0 || mode < 0) break;

        // 実行
        if (mode == 0) {
            // 0C -> W
            move_to(bwr, bwc);
            ops.push_back('W');
            A[bwr][bwc] ^= s;
        } else if (mode == 1) {
            // 1C -> W
            move_to(bpr1, bpc1);
            ops.push_back('C');
            s ^= A[bpr1][bpc1];
            move_to(bwr, bwc);
            ops.push_back('W');
            A[bwr][bwc] ^= s;
        } else { // mode == 2
            // 2C -> W
            move_to(bpr1, bpc1);
            ops.push_back('C');
            s ^= A[bpr1][bpc1];
            move_to(bpr2, bpc2);
            ops.push_back('C');
            s ^= A[bpr2][bpc2];
            move_to(bwr, bwc);
            ops.push_back('W');
            A[bwr][bwc] ^= s;
        }
        used += best_cost;
    }

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