結果
| 問題 | No.5022 XOR Printer |
| コンテスト | |
| ユーザー |
 prussian_coder
|
| 提出日時 | 2025-07-07 21:27:49 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 1,929 ms / 2,000 ms |
| コード長 | 7,366 bytes |
| コンパイル時間 | 214 ms |
| コンパイル使用メモリ | 82,224 KB |
| 実行使用メモリ | 92,784 KB |
| スコア | 5,213,702,237 |
| 最終ジャッジ日時 | 2025-07-26 12:31:49 |
| 合計ジャッジ時間 | 101,066 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
"""Heuristic solver for the XOR Grid Maximization problem."""
from __future__ import annotations
import random
import sys
import time
from typing import List, Sequence, Tuple
Cell = Tuple[int, int]
def move_commands(start: Cell, end: Cell) -> List[str]:
"""Return a list of commands to move from ``start`` to ``end``.
Movement is restricted to the four cardinal directions and no bounds
checking is performed here.
"""
cmds: List[str] = []
i, j = start
while i < end[0]:
cmds.append("D")
i += 1
while i > end[0]:
cmds.append("U")
i -= 1
while j < end[1]:
cmds.append("R")
j += 1
while j > end[1]:
cmds.append("L")
j -= 1
return cmds
def manhattan(a: Cell, b: Cell) -> int:
"""Return the Manhattan distance between two cells."""
return abs(a[0] - b[0]) + abs(a[1] - b[1])
def optimize_path(start: Cell, points: Sequence[Cell], time_limit: float) -> List[Cell]:
"""Greedy nearest-neighbour path optimisation with a 2-opt improvement."""
remaining = list(points)
path = [start]
cur = start
while remaining:
nxt = min(remaining, key=lambda p: manhattan(cur, p))
path.append(nxt)
remaining.remove(nxt)
cur = nxt
start_time = time.time()
while time.time() - start_time < time_limit:
improved = False
for i in range(1, len(path) - 2):
for j in range(i + 1, len(path) - 1):
before = manhattan(path[i - 1], path[i]) + manhattan(path[j], path[j + 1])
after = manhattan(path[i - 1], path[j]) + manhattan(path[i], path[j + 1])
if after < before:
path[i : j + 1] = reversed(path[i : j + 1])
improved = True
break
if improved:
break
if not improved:
break
return path[1:] # exclude start
class State:
"""Holds board state, cursor position and accumulated operations."""
def __init__(self, board: List[List[int]]) -> None:
self.board = board
self.n = len(board)
self.ops: List[str] = []
self.pos: Cell = (0, 0)
self.hand = 0
# ------------------------------------------------------------------
# Operations
# ------------------------------------------------------------------
def process_move(self, dest: Cell, op_limit: int) -> bool:
"""Move the cursor to ``dest`` if within the operation limit."""
cmds = move_commands(self.pos, dest)
if len(self.ops) + len(cmds) > op_limit:
return False
self.ops.extend(cmds)
self.pos = dest
return True
def process_copy(self, op_limit: int) -> bool:
"""Apply the copy operation on the current cell."""
if len(self.ops) >= op_limit:
return False
self.ops.append("C")
self.hand ^= self.board[self.pos[0]][self.pos[1]]
return True
def process_write(self, op_limit: int) -> bool:
"""Apply the write operation on the current cell."""
if len(self.ops) >= op_limit:
return False
self.ops.append("W")
self.board[self.pos[0]][self.pos[1]] ^= self.hand
return True
def get_score(self) -> int:
"""Return the total sum of all cell values."""
return sum(self.board[i][j] for i in range(self.n) for j in range(self.n))
class Solver:
"""Encapsulates the heuristic solution logic."""
def __init__(self, state: State, op_limit: int) -> None:
self.state = state
self.op_limit = op_limit - 10
self.op_limit_last = op_limit
# ------------------------------------------------------------------
# Core solving logic
# ------------------------------------------------------------------
def _prepare_bit(self, bit: int) -> None:
"""Randomly copy values until ``self.hand`` has ``bit`` set."""
attempts = 0
state = self.state
while not (state.hand < (1 << (bit + 1)) and ((state.hand >> bit) & 1)):
if attempts > state.n * state.n:
break
cell = (random.randrange(state.n), random.randrange(state.n))
if not state.process_move(cell, self.op_limit):
break
if not state.process_copy(self.op_limit):
break
attempts += 1
def _write_path(self, bit: int, path: Sequence[Cell]) -> None:
"""Follow ``path`` writing to cells whose ``bit`` is unset."""
state = self.state
path_last = path[-1]
for cell in path:
if not state.process_move(cell, self.op_limit):
break
if cell == path_last and bit != 19:
state.process_copy(self.op_limit)
break
if ((state.board[cell[0]][cell[1]] >> bit) & 1) == 0:
if not state.process_write(self.op_limit):
break
def _finalize(self) -> None:
"""Perform a final sequence of operations to maximise the score."""
state = self.state
state.process_copy(self.op_limit_last)
min_val = min(state.board[i][j] for i in range(state.n) for j in range(state.n))
min_pos = min(
[
(i, j)
for i in range(state.n)
for j in range(state.n)
if state.board[i][j] == min_val
],
key=lambda p: manhattan(state.pos, p),
)
state.process_move(min_pos, self.op_limit_last)
state.process_write(self.op_limit_last)
state.process_copy(self.op_limit_last)
state.process_write(self.op_limit_last)
def solve(self) -> int:
"""Execute the heuristic and return the resulting score."""
state = self.state
for bit in reversed(range(20)):
self._prepare_bit(bit)
target_cells = [
(i, j)
for i in range(state.n)
for j in range(state.n)
if ((state.board[i][j] >> bit) & 1) == 0
]
if not target_cells:
continue
path = optimize_path(state.pos, target_cells, 0.1)
self._write_path(bit, path)
self._finalize()
return state.get_score()
def run_solver(n: int, t: int, board: List[List[int]]) -> Tuple[int, List[str]]:
"""Convenience wrapper for executing ``Solver``."""
state = State(board)
solver = Solver(state, t)
score = solver.solve()
return score, state.ops
def main() -> None:
"""Entry point when executed as a script."""
start_time = time.time()
best_score = 0
best_ops: List[str] = []
n, t = map(int, sys.stdin.readline().split())
board_ini = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
# randomly run code and get best score
while time.time() - start_time < 1.85:
score, ops = run_solver(n, t - 10, [row[:] for row in board_ini])
if len(ops) > t:
continue
if score > best_score:
best_score = score
best_ops = ops
sys.stdout.write("\n".join(best_ops[:t]) + "\n")
sys.stderr.write(f"{best_score} {len(best_ops)}\n")
if __name__ == "__main__":
main()