結果

問題 No.5022 XOR Printer
ユーザー prussian_coder
提出日時 2025-07-14 15:34:22
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 7,245 bytes
コンパイル時間 212 ms
コンパイル使用メモリ 82,364 KB
実行使用メモリ 269,672 KB
スコア 592,298,755
最終ジャッジ日時 2025-07-26 12:40:06
合計ジャッジ時間 20,634 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 6 TLE * 44
権限があれば一括ダウンロードができます

ソースコード

diff # 

## Beam Search解法

from __future__ import annotations

import copy
import heapq
import sys

N, T = map(int, input().split())
N2 = N * N
board: list[int] = []
for _ in range(N):
    board.extend(list(map(int, input().split())))


def to_2d(position: int) -> tuple[int, int]:
    """Convert 1D position to 2D coordinates."""
    return position // N, position % N


def to_1d(x: int, y: int) -> int:
    """Convert 2D coordinates to 1D position."""
    return x * N + y


def manhattan_distance(pos1: int, pos2: int) -> int:
    """Calculate Manhattan distance between two positions."""
    x1, y1 = to_2d(pos1)
    x2, y2 = to_2d(pos2)
    return abs(x1 - x2) + abs(y1 - y2)


def generate_move_commands(start: int, end: int) -> list[str]:
    """Generate movement commands from start to end position.

    Args:
        start: Starting position (1D index)
        end: Ending position (1D index)

    Returns:
        List of movement commands ('U', 'D', 'L', 'R')
    """
    commands: list[str] = []
    x1, y1 = to_2d(start)
    x2, y2 = to_2d(end)

    current_x, current_y = x1, y1

    # Move vertically first
    while current_x < x2:
        commands.append("D")
        current_x += 1
    while current_x > x2:
        commands.append("U")
        current_x -= 1

    # Move horizontally
    while current_y < y2:
        commands.append("R")
        current_y += 1
    while current_y > y2:
        commands.append("L")
        current_y -= 1

    return commands


def process_board(
    board: list[int], commands: list[str], s: int, pos: int
) -> tuple[list[int], int, int]:
    """Process board by executing commands."""
    for command in commands:
        if command == "W":
            board[pos] ^= s
        elif command == "C":
            s ^= board[pos]
        elif command == "D":
            pos += N
        elif command == "U":
            pos -= N
        elif command == "R":
            pos += 1
        elif command == "L":
            pos -= 1
    return board, s, pos


def revert_board(board: list[int], command: str, s: int, pos: int) -> tuple[list[int], int, int]:
    """Revert board to the state before executing command."""
    if command == "W":
        board[pos] ^= s
    elif command == "C":
        s ^= board[pos]
    elif command == "D":
        pos -= N
    elif command == "U":
        pos += N
    elif command == "R":
        pos -= 1
    elif command == "L":
        pos += 1
    return board, s, pos


NEAR_POS = [set() for _ in range(N2)]
for v1 in range(N2):
    for v2 in range(N2):
        if manhattan_distance(v1, v2) <= 5:
            NEAR_POS[v1].add(v2)


class State:
    def __init__(
        self,
        board: list[int],
        s: int,
        pos: int,
        turn: int,
        score: int,
        prev_state: State | None = None,
        prev_action: tuple[str, int] | None = None,
    ) -> None:
        self.s = s
        self.board = board
        self.pos = pos
        self.turn = turn
        self.score = score
        self.prev_state = prev_state
        self.prev_action = prev_action

    def __copy__(self) -> State:
        return State(
            board=self.board[:],
            s=self.s,
            pos=self.pos,
            turn=self.turn,
            score=self.score,
            prev_state=self,
            prev_action=None,
        )

    def __eq__(self, other: State) -> bool:
        return self.score == other.score

    def __ne__(self, other: State) -> bool:
        return not self.__eq__(other)

    def __lt__(self, other: State) -> bool:
        return self.score < other.score

    def __le__(self, other: State) -> bool:
        return self.score <= other.score

    def __gt__(self, other: State) -> bool:
        return self.score > other.score

    def __ge__(self, other: State) -> bool:
        return self.score >= other.score

    def is_done(self) -> bool:
        return self.turn == T

    def is_valid(self) -> bool:
        if self.is_done():
            return True
        b = (1 << 19) - 1
        for v in self.board:
            b &= v
            if b == 0:
                return True
        return False

    def update_score(self) -> None:
        self.score = sum(self.board)

    def get_next_moves(self) -> list[tuple[str, int]]:
        next_moves = []
        for v2 in NEAR_POS[self.pos]:
            next_moves.append(("W", v2))
            next_moves.append(("C", v2))
        return next_moves

    def get_next_turn(self, pos: int) -> int:
        dist = manhattan_distance(self.pos, pos)
        return self.turn + dist + 1

    def calc_next_score(self, key: str, pos: int) -> int:
        if key == "C":
            return self.score
        new_v = self.board[pos] ^ self.s
        return self.score + new_v - self.board[pos]

    def process_move(self, key: str, pos: int) -> State:
        new_state = copy.copy(self)
        if key == "C":
            new_state.s ^= self.board[pos]
            new_state.turn = self.get_next_turn(pos)
        else:
            new_state.score = self.calc_next_score(key, pos)
            new_state.turn = self.get_next_turn(pos)
            new_state.board[pos] ^= new_state.s
        new_state.pos = pos
        new_state.prev_action = (key, self.pos)
        return new_state


class BeamSearchSolver:
    def __init__(self) -> None:
        self.beam_width = 150
        self.state_que_size = 10

    def process(self, board: list[int]) -> State:
        states: list[list[State]] = [[] for _ in range(self.state_que_size)]
        initial_state = State(
            board,
            s=0,
            pos=0,
            turn=0,
            score=sum(board),
        )
        states[0].append(initial_state)
        for turn in range(T):
            for state in states[turn % self.state_que_size]:
                next_moves = state.get_next_moves()
                for key, pos in next_moves:
                    next_turn = state.get_next_turn(pos)
                    next_t = next_turn % self.state_que_size
                    if next_turn > T:
                        continue
                    score = state.calc_next_score(key, pos)
                    if score < state.score:
                        continue
                    if len(states[next_t]) < self.beam_width:
                        new_state = state.process_move(key, pos)
                        if new_state.is_valid():
                            heapq.heappush(states[next_t], new_state)
                    elif score > states[next_t][0].score:
                        new_state = state.process_move(key, pos)
                        if new_state.is_valid():
                            heapq.heappop(states[next_t])
                            heapq.heappush(states[next_t], new_state)
            states[turn % self.state_que_size] = []
        return max(states[0])


solver = BeamSearchSolver()
best_state = solver.process(board)
print(best_state.board, file=sys.stderr)

actions = []
while best_state.prev_state is not None:
    pos = best_state.pos
    key, last_pos = best_state.prev_action
    actions.append(key)
    actions.extend(generate_move_commands(last_pos, pos)[::-1])
    best_state = best_state.prev_state

actions.reverse()
for a in actions:
    print(a)
0