結果

問題 No.5022 XOR Printer
コンテスト
ユーザー prussian_coder
提出日時 2025-07-10 13:10:28
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,650 bytes
コンパイル時間 499 ms
コンパイル使用メモリ 82,412 KB
実行使用メモリ 297,992 KB
スコア 4,533,292,127
最終ジャッジ日時 2025-07-26 12:36:18
合計ジャッジ時間 99,870 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 48 TLE * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

# 操作列のビームサーチ

# 1回の操作を1ステップとしたビームサーチをする
# 評価関数はスコア盤面の合計値

from __future__ import annotations

import heapq
import sys
from dataclasses import dataclass, field
from typing import List


@dataclass(order=True)
class BeamState:
    priority: int
    score: int = field(compare=False)
    board: List[List[int]] = field(compare=False)
    x: int = field(compare=False)
    y: int = field(compare=False)
    s: int = field(compare=False)
    ops: List[str] = field(compare=False)


def board_sum(board: List[List[int]]) -> int:
    return sum(sum(row) for row in board)


def apply_op(state: BeamState, op: str, n: int) -> BeamState | None:
    x, y, s_val = state.x, state.y, state.s
    board = [row[:] for row in state.board]
    score = state.score
    if op == "U":
        if x == 0:
            return None
        x -= 1
    elif op == "D":
        if x == n - 1:
            return None
        x += 1
    elif op == "L":
        if y == 0:
            return None
        y -= 1
    elif op == "R":
        if y == n - 1:
            return None
        y += 1
    elif op == "C":
        s_val ^= board[x][y]
    elif op == "W":
        old = board[x][y]
        new_val = old ^ s_val
        board[x][y] = new_val
        score += new_val - old
    else:
        return None

    ops = state.ops + [op]
    return BeamState(priority=-score, score=score, board=board, x=x, y=y, s=s_val, ops=ops)


def beam_search(board: List[List[int]], t: int, width: int) -> List[str]:
    n = len(board)
    start_score = board_sum(board)
    start = BeamState(
        priority=-start_score,
        score=start_score,
        board=[row[:] for row in board],
        x=0,
        y=0,
        s=0,
        ops=[],
    )
    beam = [start]
    for _ in range(t):
        candidates: list[tuple[int, BeamState]] = []
        for state in beam:
            for op in ["U", "D", "L", "R", "W", "C"]:
                next_state = apply_op(state, op, n)
                if next_state is not None:
                    heapq.heappush(candidates, (next_state.priority, next_state))
        beam = []
        for _ in range(min(width, len(candidates))):
            priority, st = heapq.heappop(candidates)
            beam.append(st)
    best = max(beam, key=lambda s: s.score)
    return best.ops


def main() -> None:
    n, t = map(int, sys.stdin.readline().split())
    board = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
    ops = beam_search(board, t, width=100)
    sys.stdout.write("\n".join(ops) + "\n")


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