結果

問題 No.5022 XOR Printer
ユーザー prussian_coder
提出日時 2025-07-23 15:09:00
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 247 ms / 2,000 ms
コード長 4,207 bytes
コンパイル時間 395 ms
コンパイル使用メモリ 82,376 KB
実行使用メモリ 80,256 KB
スコア 4,757,586,375
最終ジャッジ日時 2025-07-26 12:41:45
合計ジャッジ時間 13,221 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

# 貪欲解法2
# ターン数のもとで下記の操作の中で最もスコアが良くなる選択を選ぶ貪欲法
## 現在の位置からマンハッタン距離がdのセルに移動し、操作Wを実施する（d <= 5）
## 現在の位置からマンハッタン距離がd1のセルに移動し操作Cを実施した後、距離d2だけ移動して操作Wを実施する（d1+d2 <= 5）



from __future__ import annotations

import sys
from typing import List, Tuple

Cell = Tuple[int, int]


def move_commands(start: Cell, end: Cell) -> List[str]:
    """Return commands to move from start to end using UDLR moves."""
    cmds: List[str] = []
    x, y = start
    tx, ty = end
    while x < tx:
        cmds.append("D")
        x += 1
    while x > tx:
        cmds.append("U")
        x -= 1
    while y < ty:
        cmds.append("R")
        y += 1
    while y > ty:
        cmds.append("L")
        y -= 1
    return cmds


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:
        remaining = t - len(ops)
        best_diff = 0
        best_seq: List[str] | None = None

        # Option A: move up to distance 5 and write
        for dx in range(-5, 6):
            for dy in range(-5, 6):
                dist = abs(dx) + abs(dy)
                if dist == 0 or dist > 5:
                    continue
                nx, ny = x + dx, y + dy
                if not (0 <= nx < n and 0 <= ny < n):
                    continue
                cost = dist + 1
                if cost > remaining:
                    continue
                diff = (board[nx][ny] ^ s_val) - board[nx][ny]
                if diff > best_diff:
                    best_diff = diff
                    path = move_commands((x, y), (nx, ny))
                    best_seq = path + ["W"]

        # Option B: move to cell1, copy, move to cell2, write (total dist <= 5)
        for dx1 in range(-5, 6):
            for dy1 in range(-5, 6):
                d1 = abs(dx1) + abs(dy1)
                if d1 > 5:
                    continue
                nx1, ny1 = x + dx1, y + dy1
                if not (0 <= nx1 < n and 0 <= ny1 < n):
                    continue
                for dx2 in range(-5, 6):
                    for dy2 in range(-5, 6):
                        d2 = abs(dx2) + abs(dy2)
                        if d1 + d2 > 5:
                            continue
                        nx2, ny2 = nx1 + dx2, ny1 + dy2
                        if not (0 <= nx2 < n and 0 <= ny2 < n):
                            continue
                        cost = d1 + d2 + 2
                        if cost > remaining:
                            continue
                        s_prime = s_val ^ board[nx1][ny1]
                        diff = (board[nx2][ny2] ^ s_prime) - board[nx2][ny2]
                        if diff > best_diff:
                            best_diff = diff
                            seq = move_commands((x, y), (nx1, ny1))
                            seq.append("C")
                            seq.extend(move_commands((nx1, ny1), (nx2, ny2)))
                            seq.append("W")
                            best_seq = seq

        if best_seq and best_diff > 0:
            ops.extend(best_seq)
            # apply operations to board, x, y, s_val
            pos_x, pos_y = x, y
            for op in best_seq:
                if op == "U":
                    pos_x -= 1
                elif op == "D":
                    pos_x += 1
                elif op == "L":
                    pos_y -= 1
                elif op == "R":
                    pos_y += 1
                elif op == "C":
                    s_val ^= board[pos_x][pos_y]
                elif op == "W":
                    board[pos_x][pos_y] ^= s_val
            x, y = pos_x, pos_y
        else:
            if len(ops) < t:
                ops.append("C")
                s_val ^= board[x][y]
            else:
                break

    sys.stdout.write("\n".join(ops[:t]) + "\n")


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