結果

問題 No.5022 XOR Printer
ユーザー prussian_coder
提出日時 2025-07-10 12:55:52
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 49 ms / 2,000 ms
コード長 2,624 bytes
コンパイル時間 442 ms
コンパイル使用メモリ 82,368 KB
実行使用メモリ 57,760 KB
スコア 4,727,743,751
最終ジャッジ日時 2025-07-26 12:34:31
合計ジャッジ時間 4,498 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

# 貪欲法解法

# ターン数上限に至るまで以下を繰り返す  

# 今の位置から前後左右に移動して操作Wをした時、最もスコアが良くなる方に貪欲に移動する
# どの方向へ移動してもスコアが良くならない場合は、CLURDのいずれかをランダムに選ぶ（盤面から出ないこと）


from __future__ import annotations

import random
import sys


def main() -> None:
    n, t = map(int, sys.stdin.readline().split())
    board = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

    x, y = 0, 0
    s_val = 0
    ops: list[str] = []

    while len(ops) < t:
        if t - len(ops) >= 2:
            best_diff = -1
            best_move: str | None = None
            best_pos = (x, y)

            if x > 0:
                diff = (board[x - 1][y] ^ s_val) - board[x - 1][y]
                if diff > best_diff:
                    best_diff = diff
                    best_move = "U"
                    best_pos = (x - 1, y)
            if x + 1 < n:
                diff = (board[x + 1][y] ^ s_val) - board[x + 1][y]
                if diff > best_diff:
                    best_diff = diff
                    best_move = "D"
                    best_pos = (x + 1, y)
            if y > 0:
                diff = (board[x][y - 1] ^ s_val) - board[x][y - 1]
                if diff > best_diff:
                    best_diff = diff
                    best_move = "L"
                    best_pos = (x, y - 1)
            if y + 1 < n:
                diff = (board[x][y + 1] ^ s_val) - board[x][y + 1]
                if diff > best_diff:
                    best_diff = diff
                    best_move = "R"
                    best_pos = (x, y + 1)

            if best_diff > 0 and best_move is not None:
                ops.append(best_move)
                x, y = best_pos
                ops.append("W")
                board[x][y] ^= s_val
                continue

        available_ops: list[str] = ["C"]
        if x > 0:
            available_ops.append("U")
        if x + 1 < n:
            available_ops.append("D")
        if y > 0:
            available_ops.append("L")
        if y + 1 < n:
            available_ops.append("R")

        op = random.choice(available_ops)
        ops.append(op)
        if op == "C":
            s_val ^= board[x][y]
        elif op == "U":
            x -= 1
        elif op == "D":
            x += 1
        elif op == "L":
            y -= 1
        elif op == "R":
            y += 1

    sys.stdout.write("\n".join(ops) + "\n")


if __name__ == "__main__":
    main()
0