結果
| 問題 |
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 |
ソースコード
## 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)