結果
| 問題 |
No.5022 XOR Printer
|
| コンテスト | |
| ユーザー |
 prussian_coder
|
| 提出日時 | 2025-07-08 16:09:02 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 1,779 ms / 2,000 ms |
| コード長 | 19,243 bytes |
| コンパイル時間 | 813 ms |
| コンパイル使用メモリ | 81,988 KB |
| 実行使用メモリ | 105,508 KB |
| スコア | 5,223,674,328 |
| 最終ジャッジ日時 | 2025-07-26 12:33:15 |
| 合計ジャッジ時間 | 79,771 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
from __future__ import annotations
import random
import sys
from typing import Optional
random.seed(0)
# Constants
MAX_BIT = 20
MAX_SEE_BIT = 8
DEFAULT_TARGET_BIT = 19
ANNEALING_DECAY = 0.99
INITIAL_ACCEPT_PROB = 1.0
# Input parsing
N, T = map(int, input().split())
N2 = N * N
board: list[int] = []
for _ in range(N):
board.extend(list(map(int, input().split())))
BINARY_VALS = [1 << i for i in range(MAX_BIT + 1)]
BIT_MASK = BINARY_VALS[-1] - 1
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
def get_one_intermediate_positions_2d(start_pos: int, end_pos: int) -> list[tuple[int, int]]:
"""Get intermediate position pairs for 2D coordinates."""
start_x, start_y = to_2d(start_pos)
end_x, end_y = to_2d(end_pos)
if start_x > end_x:
start_x, end_x = end_x, start_x
if start_y > end_y:
start_y, end_y = end_y, start_y
candidates = []
for x in range(start_x, end_x + 1):
for y in range(start_y, end_y + 1):
if x != end_x or y != end_y:
candidates.append(to_1d(x, y))
return candidates
def get_two_intermediate_positions_1d(start: int, end: int) -> list[tuple[int, int]]:
"""Get intermediate position pairs for 1D coordinates."""
if start <= end:
left, right = start, end
else:
left, right = -start, -end
return [(abs(m1), abs(m2)) for m1 in range(left, right + 1) for m2 in range(m1, right + 1)]
def get_two_intermediate_positions_2d(start_pos: int, end_pos: int) -> list[tuple[int, int]]:
"""Get intermediate position pairs for 2D coordinates."""
start_x, start_y = to_2d(start_pos)
end_x, end_y = to_2d(end_pos)
x_pairs = get_two_intermediate_positions_1d(start_x, end_x)
y_pairs = get_two_intermediate_positions_1d(start_y, end_y)
candidates = []
for x1, x2 in x_pairs:
for y1, y2 in y_pairs:
pos1 = to_1d(x1, y1)
pos2 = to_1d(x2, y2)
if pos1 != pos2 and pos2 != end_pos:
candidates.append((pos1, pos2))
return candidates
def is_valid_state(state: int, target_bit: int) -> bool:
"""Check if state is valid for the given target bit."""
return BINARY_VALS[target_bit] <= state < BINARY_VALS[target_bit + 1]
class RouteOptimizer:
"""Optimizes routes using 2-opt hill climbing with simulated annealing."""
def generate_optimal_route(
self, start_pos: int, board: list[int], target_bit: int
) -> list[int]:
"""Generate optimized route to visit all targets.
Args:
start_pos: Starting position
board: Game board state
target_bit: Target bit for optimization
Returns:
Optimized route as list of positions
"""
targets = self._find_target_positions(board, target_bit)
initial_route = self._build_nearest_neighbor_route(start_pos, targets, target_bit)
optimized_route = self._apply_2opt_optimization(initial_route, target_bit)
return optimized_route
def _find_target_positions(self, board: list[int], target_bit: int) -> list[int]:
"""Find all positions that need to be visited."""
return [i for i in range(N2) if (board[i] >> target_bit) & 1 == 0]
def _build_nearest_neighbor_route(
self, start_pos: int, targets: list[int], target_bit: int
) -> list[int]:
"""Build initial route using nearest neighbor heuristic."""
route = [start_pos]
current_pos = start_pos
remaining_targets = set(targets)
# Build route using nearest neighbor
while remaining_targets:
nearest = min(remaining_targets, key=lambda x: manhattan_distance(current_pos, x))
route.append(nearest)
remaining_targets.remove(nearest)
current_pos = nearest
# Ensure the last position can be the final destination
self._adjust_final_position(route, target_bit)
return route
def _adjust_final_position(self, route: list[int], target_bit: int) -> None:
"""Adjust route to ensure last position is valid as final destination."""
for i in reversed(range(len(route))):
if self._can_be_final_position(board[route[i]], target_bit):
route[i], route[-1] = route[-1], route[i]
break
def _apply_2opt_optimization(self, route: list[int], target_bit: int) -> list[int]:
"""Apply 2-opt optimization with simulated annealing."""
accept_probability = INITIAL_ACCEPT_PROB
while True:
improved = False
indices = list(range(1, len(route) + 1))
random.shuffle(indices)
for i, idx1 in enumerate(indices):
for idx2 in indices[i + 1 :]:
if idx1 > idx2:
idx1, idx2 = idx2, idx1
if not self._is_valid_2opt_move(route, idx1, idx2, target_bit):
continue
delta = self._calculate_2opt_improvement(route, idx1, idx2)
if self._should_accept_move(delta, accept_probability):
route[idx1:idx2] = reversed(route[idx1:idx2])
improved = True
break
if improved:
break
if not improved:
break
accept_probability *= ANNEALING_DECAY
return route
def _is_valid_2opt_move(self, route: list[int], idx1: int, idx2: int, target_bit: int) -> bool:
"""Check if 2-opt move is valid."""
return not (
idx2 == len(route) and not self._can_be_final_position(board[route[idx1]], target_bit)
)
def _calculate_2opt_improvement(self, route: list[int], idx1: int, idx2: int) -> int:
"""Calculate distance improvement from 2-opt move."""
if idx2 == len(route):
return manhattan_distance(route[idx1 - 1], route[idx2 - 1]) - manhattan_distance(
route[idx1 - 1], route[idx1]
)
return (
manhattan_distance(route[idx1 - 1], route[idx2 - 1])
+ manhattan_distance(route[idx1], route[idx2])
- manhattan_distance(route[idx1 - 1], route[idx1])
- manhattan_distance(route[idx2 - 1], route[idx2])
)
def _should_accept_move(self, delta: int, accept_probability: float) -> bool:
"""Determine if a move should be accepted."""
return delta < 0 or (delta == 0 and random.random() < accept_probability)
def _can_be_final_position(self, cell_value: int, target_bit: int) -> bool:
"""Check if position can be the final destination."""
return target_bit == DEFAULT_TARGET_BIT or is_valid_state(cell_value ^ BIT_MASK, target_bit)
class WriteCopyPlanner:
"""Plans write and copy operations for optimal path execution."""
def __init__(self, target_bit: int):
self.target_bit = target_bit
self.see_bit = min(target_bit, MAX_SEE_BIT)
def generate_execution_plan(
self, route: list[int], board: list[int], initial_state: int
) -> list[str]:
"""Generate complete execution plan for the route.
Args:
route: Route to execute
board: Game board state
initial_state: Initial state value
Returns:
List of commands to execute
"""
# Initialize dynamic programming tables
dp_table, transition_table = self._initialize_dp_tables(len(route))
# Find optimal starting states
start_states = self._find_optimal_start_states(route, board, initial_state, dp_table)
# Calculate board top bits for efficiency
board_tops = self._calculate_board_tops(board)
# Fill DP table
self._fill_dp_table(route, board, dp_table, transition_table, board_tops)
# Generate commands from optimal path
commands = self._reconstruct_commands(route, dp_table, transition_table, start_states)
return commands
def _initialize_dp_tables(
self, route_length: int
) -> tuple[list[list[float]], list[list[tuple]]]:
"""Initialize dynamic programming tables."""
states_count = 1 << self.see_bit
dp_table = [[float("inf")] * states_count for _ in range(route_length - 1)]
transition_table = [[(None, None, None)] * states_count for _ in range(route_length - 1)]
return dp_table, transition_table
def _find_optimal_start_states(
self, route: list[int], board: list[int], initial_state: int, dp_table: list[list[float]]
) -> list[Optional[int]]:
"""Find optimal starting states for each state configuration."""
start_states = [None] * (1 << self.see_bit)
start_pos = route[0]
for pos in range(N2):
if not is_valid_state(board[pos] ^ initial_state, self.target_bit):
continue
state = board[pos] ^ initial_state
state_top = self._extract_top_bits(state)
distance = manhattan_distance(start_pos, pos) + manhattan_distance(pos, route[1])
if dp_table[0][state_top] > distance:
dp_table[0][state_top] = distance
start_states[state_top] = pos
return start_states
def _calculate_board_tops(self, board: list[int]) -> list[int]:
"""Calculate top bits for all board positions."""
return [
(value % (1 << self.target_bit)) // (1 << (self.target_bit - self.see_bit))
for value in board
]
def _extract_top_bits(self, state: int) -> int:
"""Extract top bits from state."""
return (state % (1 << self.see_bit)) // (1 << (self.target_bit - self.see_bit))
def _fill_dp_table(
self,
route: list[int],
board: list[int],
dp_table: list[list[float]],
transition_table: list[list[tuple]],
board_tops: list[int],
) -> None:
"""Fill the dynamic programming table."""
for i in range(1, len(route) - 1):
for state in range(1 << self.see_bit):
if dp_table[i - 1][state] == float("inf"):
continue
# Direct write without copy
self._process_direct_write(i, state, route, board_tops, dp_table, transition_table)
# Write with intermediate copies
if i > 1:
self._process_copy_operations(
i, state, route, board, board_tops, dp_table, transition_table
)
def _process_direct_write(
self,
i: int,
state: int,
route: list[int],
board_tops: list[int],
dp_table: list[list[float]],
transition_table: list[list[tuple]],
) -> None:
"""Process direct write operation."""
current_state = state
value = board_tops[route[i]] ^ current_state
cost = dp_table[i - 1][state] - self._calculate_bit_score(value)
if dp_table[i][current_state] > cost:
dp_table[i][current_state] = cost
transition_table[i][current_state] = (state, None, None)
def _process_copy_operations(
self,
i: int,
state: int,
route: list[int],
board: list[int],
board_tops: list[int],
dp_table: list[list[float]],
transition_table: list[list[tuple]],
) -> None:
"""Process copy operations at intermediate positions."""
for pos1, pos2 in get_two_intermediate_positions_2d(route[i - 1], route[i]):
new_state = self._calculate_copy_state(
state, pos1, pos2, route[i - 1], board, board_tops
)
if new_state is None:
continue
value = board_tops[route[i]] ^ new_state
cost = dp_table[i - 1][state] + 2 - self._calculate_bit_score(value)
if dp_table[i][new_state] > cost:
dp_table[i][new_state] = cost
transition_table[i][new_state] = (state, pos1, pos2)
def _calculate_copy_state(
self,
state: int,
pos1: int,
pos2: int,
route_pos: int,
board: list[int],
board_tops: list[int],
) -> Optional[int]:
"""Calculate new state after copy operations."""
if pos1 == route_pos:
if board[pos2] ^ BIT_MASK >= BINARY_VALS[self.target_bit] or not is_valid_state(
board[pos1] ^ board[pos2], self.target_bit
):
return None
return board_tops[pos1] ^ board_tops[pos2]
else:
if (
board[pos1] ^ BIT_MASK >= BINARY_VALS[self.target_bit]
or board[pos2] ^ BIT_MASK >= BINARY_VALS[self.target_bit]
):
return None
return state ^ board_tops[pos1] ^ board_tops[pos2]
def _reconstruct_commands(
self,
route: list[int],
dp_table: list[list[float]],
transition_table: list[list[tuple]],
start_states: list[Optional[int]],
) -> list[str]:
"""Reconstruct commands from optimal path."""
commands = []
optimal_state = dp_table[-1].index(min(dp_table[-1]))
# Reconstruct path backwards
for i in reversed(range(2, len(route) - 1)):
commands.append("W")
prev_state, pos1, pos2 = transition_table[i][optimal_state]
if pos1 is None:
commands.extend(generate_move_commands(route[i - 1], route[i]))
else:
self._add_copy_commands(commands, route[i - 1], pos1, pos2, route[i])
optimal_state = prev_state
# Add initial commands
commands.append("W")
initial_pos = start_states[optimal_state]
commands.extend(generate_move_commands(initial_pos, route[1]))
commands.append("C")
commands.extend(generate_move_commands(route[0], initial_pos))
commands.reverse()
# Add final movement and copy
commands.extend(generate_move_commands(route[-2], route[-1]))
if self.target_bit == 19:
commands.append("W")
else:
commands.append("C")
return commands
def _add_copy_commands(
self, commands: list[str], start_pos: int, pos1: int, pos2: int, end_pos: int
) -> None:
"""Add copy-related movement commands."""
commands.extend(generate_move_commands(pos2, end_pos))
commands.append("C")
commands.extend(generate_move_commands(pos1, pos2))
commands.append("C")
commands.extend(generate_move_commands(start_pos, pos1))
def _calculate_bit_score(self, state_top: int) -> int:
"""Calculate bit score for state optimization."""
count = 0
for i in reversed(range(self.see_bit)):
if not (state_top >> i & 1):
return count
count += 1
return count
def postprocess_board(
board: list[int], commands: list[str], s: int, pos: int
) -> tuple[list[int], int, int]:
"""Postprocess board to optimize it."""
while True:
min_pos = board.index(min(board))
necessary_steps = len(commands) + manhattan_distance(pos, min_pos) + 4
if necessary_steps > T:
last_command = commands.pop()
board, s, pos = revert_board(board, last_command, s, pos)
continue
best_s = 10**6
best_v = None
for v in get_one_intermediate_positions_2d(pos, min_pos):
s2 = board[v] ^ s
if s2 > best_s:
best_s = s2
best_v = v
if best_v is None:
last_command = commands.pop()
board, s, pos = revert_board(board, last_command, s, pos)
continue
added_commands = (
generate_move_commands(pos, best_v)
+ ["C"]
+ generate_move_commands(best_v, min_pos)
+ ["W", "C", "W"]
)
commands.extend(added_commands)
board, s, pos = process_board(board, added_commands, s, pos)
return board, s, pos, commands
def solve_puzzle(board: list[int]) -> None:
"""Main puzzle solving function."""
pos = to_1d(0, 0)
s = 0
commands = []
# Generate optimal route
for target_bit in reversed(range(MAX_BIT)):
route_optimizer = RouteOptimizer()
optimal_route = route_optimizer.generate_optimal_route(pos, board, target_bit)
# Generate execution plan
planner = WriteCopyPlanner(target_bit)
execution_commands = planner.generate_execution_plan(optimal_route, board, s)
board, s, pos = process_board(board, execution_commands, s, pos)
commands.extend(execution_commands)
if len(commands) > T:
break
board, s, pos, commands = postprocess_board(board, commands, s, pos)
for command in commands[:T]:
print(command)
print(sum(board), file=sys.stderr)
solve_puzzle(board)