結果

問題 No.5022 XOR Printer
ユーザー prussian_coder
提出日時 2025-07-24 13:12:48
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 102 ms / 2,000 ms
コード長 2,966 bytes
コンパイル時間 513 ms
コンパイル使用メモリ 82,284 KB
実行使用メモリ 79,860 KB
スコア 5,130,982,535
最終ジャッジ日時 2025-07-26 12:43:55
合計ジャッジ時間 7,201 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

# 貪欲解法+a https://yukicoder.me/submissions/1106586

# 操作Wを実施することでスコアが上がるセルのうち最も近いセルを選び、操作Wをする
# 操作Wを実施することでスコアが上がるセルが存在しない場合は、ランダムに1つのセルを選び移動して、操作Cをする
# ただし、19bit以下のビットが全て0になっている場合は操作Wではなく操作Cを実行する

from __future__ import annotations

import random
import sys
from typing import List, Tuple

Cell = Tuple[int, int]


def is_valid_board(board: list[list[int]]) -> bool:
    b = (1 << 19) - 1
    for row in board:
        for v in row:
            b &= v
        if b == 0:
            return True
    return False


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 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] = []
    rng = random.Random(0)

    while len(ops) < t:
        best_cell: Cell | None = None
        best_dist = 10**9
        for i in range(n):
            for j in range(n):
                if (board[i][j] ^ s_val) > board[i][j]:
                    d = abs(x - i) + abs(y - j)
                    if d < best_dist:
                        best_dist = d
                        best_cell = (i, j)
        if best_cell is not None:
            path = move_commands((x, y), best_cell)
            if len(ops) + len(path) + 1 > t:
                break
            ops.extend(path)
            x, y = best_cell
            ops.append("W")
            board[x][y] ^= s_val
            is_valid = is_valid_board(board)
            # 操作Wを実行した後、19bit以下のビットが全て0になっている場合は操作Wではなく操作Cを実行する
            if not is_valid:
                ops.pop()
                ops.append("C")
                board[x][y] ^= s_val
                s_val ^= board[x][y]
        else:
            rand_cell = (rng.randrange(n), rng.randrange(n))
            # 最初の操作の場合は19bit目が1であるセルに移動して操作Cをする
            if len(ops) == 0 and (board[rand_cell[0]][rand_cell[1]] >> 19) & 1 == 0:
                continue
            path = move_commands((x, y), rand_cell)
            if len(ops) + len(path) + 1 > t:
                break
            ops.extend(path)
            x, y = rand_cell
            ops.append("C")
            s_val ^= board[x][y]

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


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