結果

問題 No.5022 XOR Printer
コンテスト
ユーザー Ang1077
提出日時 2025-07-26 13:20:12
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 4 ms / 2,000 ms
コード長 2,936 bytes
コンパイル時間 3,152 ms
コンパイル使用メモリ 285,932 KB
実行使用メモリ 7,716 KB
スコア 4,858,566,822
最終ジャッジ日時 2025-07-26 13:20:18
合計ジャッジ時間 5,839 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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;
        // 残りが2未満なら(CとWができない)終了
        if (rem < 2) break;

        // すべてのコピー地点P=(pr,pc)と書き込み地点Q=(wr,wc)を全探索し、
        // 残り手数内で到達でき、スコア増分が最大のものを貪欲に選ぶ
        long long best_delta = 0; // 正の改善のみ採用
        int bpr = -1, bpc = -1, bwr = -1, bwc = -1;
        int best_cost = 0;

        for (int pr = 0; pr < N; ++pr) {
            for (int pc = 0; pc < N; ++pc) {
                int cost_to_p = manhattan(r, c, pr, pc);
                // ここでCを1手
                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 cost_p_to_w = manhattan(pr, pc, wr, wc);
                        int total_cost = cost_to_p + 1 + cost_p_to_w + 1; // 移動 + C + 移動 + 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;
                            bpr = pr; bpc = pc; bwr = wr; bwc = wc;
                            best_cost = total_cost;
                        }
                    }
                }
            }
        }

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

        // 実行：現在位置→P 移動、C、P→Q 移動、W
        move_to(bpr, bpc);
        ops.push_back('C');
        s ^= A[bpr][bpc];

        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