結果

問題 No.5022 XOR Printer
コンテスト
ユーザー prussian_coder
提出日時 2025-07-23 15:48:09
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 63 ms / 2,000 ms
コード長 3,876 bytes
コンパイル時間 568 ms
コンパイル使用メモリ 82,452 KB
実行使用メモリ 72,248 KB
スコア 4,575,659,115
最終ジャッジ日時 2025-07-26 12:41:52
合計ジャッジ時間 5,703 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

# 上のbitから順に変えていくジグザグ巡回解法

# 盤面全体を走査し、現在の保持値 s_val の b 桁目のみが 1 となるセルを探索して最も近いセルに移動し、C を実行します。
# その後、最寄りの角まで移動し、そこから snake_order で得たジグザグ経路を辿って全セルを巡回します。
# 巡回中、セル値を s_val で XOR することで改善が見込める場合は W を出力します。

from __future__ import annotations

import sys
from typing import List, Tuple

Cell = Tuple[int, int]


def move_commands(start: Cell, end: Cell) -> List[str]:
    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 nearest_corner(pos: Cell, n: int) -> Cell:
    corners = [(0, 0), (0, n - 1), (n - 1, 0), (n - 1, n - 1)]
    return min(corners, key=lambda c: abs(pos[0] - c[0]) + abs(pos[1] - c[1]))


def snake_order(n: int, start_corner: Cell) -> List[Cell]:
    order: List[Cell] = []
    if start_corner == (0, 0):
        for i in range(n):
            if i % 2 == 0:
                order.extend((i, j) for j in range(n))
            else:
                order.extend((i, j) for j in reversed(range(n)))
    elif start_corner == (0, n - 1):
        for i in range(n):
            if i % 2 == 0:
                order.extend((i, j) for j in reversed(range(n)))
            else:
                order.extend((i, j) for j in range(n))
    elif start_corner == (n - 1, 0):
        for i in reversed(range(n)):
            if (n - 1 - i) % 2 == 0:
                order.extend((i, j) for j in range(n))
            else:
                order.extend((i, j) for j in reversed(range(n)))
    else:  # (n - 1, n - 1)
        for i in reversed(range(n)):
            if (n - 1 - i) % 2 == 0:
                order.extend((i, j) for j in reversed(range(n)))
            else:
                order.extend((i, j) for j in range(n))
    return order


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] = []

    for b in reversed(range(20)):
        if len(ops) >= t:
            break

        best_cell: Cell | None = None
        best_dist = 10**9
        for i in range(n):
            for j in range(n):
                new_s = s_val ^ board[i][j]
                if new_s < (1 << (b + 1)) and ((new_s >> b) & 1):
                    d = abs(x - i) + abs(y - j)
                    if d < best_dist:
                        best_dist = d
                        best_cell = (i, j)
        if best_cell is None:
            continue
        path = move_commands((x, y), best_cell)
        if len(ops) + len(path) + 1 > t:
            break
        ops.extend(path)
        x, y = best_cell
        ops.append("C")
        s_val ^= board[x][y]

        corner = nearest_corner((x, y), n)
        path = move_commands((x, y), corner)
        if len(ops) + len(path) > t:
            break
        ops.extend(path)
        x, y = corner

        snake = snake_order(n, corner)
        for cell in snake:
            if len(ops) >= t:
                break
            if (x, y) != cell:
                path = move_commands((x, y), cell)
                if len(ops) + len(path) > t:
                    break
                ops.extend(path)
                x, y = cell
            if board[x][y] ^ s_val > board[x][y] and len(ops) < t:
                board[x][y] ^= s_val
                ops.append("W")

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


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