結果
| 問題 |
No.5022 XOR Printer
|
| コンテスト | |
| ユーザー |
 prussian_coder
|
| 提出日時 | 2025-07-23 17:01:49 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 1,779 ms / 2,000 ms |
| コード長 | 7,673 bytes |
| コンパイル時間 | 379 ms |
| コンパイル使用メモリ | 82,700 KB |
| 実行使用メモリ | 92,220 KB |
| スコア | 5,205,187,746 |
| 最終ジャッジ日時 | 2025-07-26 12:43:44 |
| 合計ジャッジ時間 | 92,801 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
# https://yukicoder.me/submissions/1106514 について、最後の10ターンで以下の処理をすることで
# 最も小さいセルとs_valを入れ替えスコアを上げる
# 現在の位置から3手でいけるセルのうち、操作Cを適用することでs_valの値が最も大きくなるセルに移動して、操作Cを適用する
# boardのうち最も値が小さいセルに移動して、操作W→操作C→操作Wを適用する
# 手数が1000手以下であれば採用する。
from __future__ import annotations
import random
import sys
import time
from typing import List, Sequence, Tuple
Cell = Tuple[int, int]
TIME_LIMIT = 1.7 # 時間制限（秒）
def move_commands(start: Cell, end: Cell) -> List[str]:
cmds: List[str] = []
x, y = start
tx, ty = end
while x < tx:
cmds.append("D")
x += 1
while x > tx:
cmds.append("U")
x -= 1
while y < ty:
cmds.append("R")
y += 1
while y > ty:
cmds.append("L")
y -= 1
return cmds
def nearest_corner(pos: Cell, n: int) -> Cell:
corners = [(0, 0), (0, n - 1), (n - 1, 0), (n - 1, n - 1)]
return min(corners, key=lambda c: abs(pos[0] - c[0]) + abs(pos[1] - c[1]))
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]:
"""Nearest neighbour with light 2-opt optimisation."""
remaining = list(points)
path = [start]
cur = start
while remaining:
if len(remaining) > 1:
candidates = sorted(remaining, key=lambda p: manhattan(cur, p))
top_k = min(3, len(candidates))
nxt = random.choice(candidates[:top_k])
else:
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:]
def is_valid_board(board: list[list[int]]) -> bool:
b = (1 << 19) - 1
for row in board:
for v in row:
b &= v
if b == 0:
return True
return False
def calculate_score(board: list[list[int]]) -> int:
"""ボードの現在の状態からスコアを計算"""
# すべてのセルの値の論理積を計算
return sum(sum(a) for a in board)
def solve_once(n: int, t: int, board: list[list[int]]) -> Tuple[List[str], int]:
"""一回分の解法実行"""
# ボードのコピーを作成
board_copy = [row[:] for row in board]
t2 = t - 10
x, y = 0, 0
s_val = 0
ops: List[str] = []
for b in reversed(range(20)):
if not is_valid_board(board_copy):
break
if len(ops) >= t2:
break
best_cell: Cell | None = None
best_dist = 10**9
candidates = []
for i in range(n):
for j in range(n):
new_s = s_val ^ board_copy[i][j]
if new_s < (1 << (b + 1)) and ((new_s >> b) & 1):
d = abs(x - i) + abs(y - j)
candidates.append((i, j, d))
if not candidates:
continue
# ランダム要素：近い候補からランダムに選択
if len(candidates) > 1:
candidates.sort(key=lambda x: x[2])
top_k = min(3, len(candidates))
best_i, best_j, _ = random.choice(candidates[:top_k])
best_cell = (best_i, best_j)
else:
best_cell = min(candidates, key=lambda x: x[2])[:2]
if best_cell is None:
continue
path = move_commands((x, y), best_cell)
if len(ops) + len(path) + 1 > t2:
break
ops.extend(path)
x, y = best_cell
ops.append("C")
s_val ^= board_copy[x][y]
corner = nearest_corner((x, y), n)
path = move_commands((x, y), corner)
if len(ops) + len(path) > t2:
break
ops.extend(path)
x, y = corner
targets = [(i, j) for i in range(n) for j in range(n) if ((board_copy[i][j] >> b) & 1) == 0]
optimized_route = optimize_path((x, y), targets, 0.05)
for cell in optimized_route:
if len(ops) >= t2:
break
if (x, y) != cell:
path = move_commands((x, y), cell)
if len(ops) + len(path) > t2:
break
ops.extend(path)
x, y = cell
if board_copy[x][y] ^ s_val > board_copy[x][y] and len(ops) < t2:
board_copy[x][y] ^= s_val
is_valid = is_valid_board(board_copy)
if is_valid:
ops.append("W")
else:
board_copy[x][y] ^= s_val
ops.append("C")
s_val ^= board_copy[x][y]
# 現在の位置から距離3以内のもののうち、操作Cをして最もs_valが大きくなるものを選ぶ
best_s = 0
best_cell = None
for i in range(n):
for j in range(n):
if manhattan((x, y), (i, j)) <= 3:
new_s = s_val ^ board_copy[i][j]
if new_s > best_s:
best_s = new_s
best_cell = (i, j)
if best_cell is not None:
ops.extend(move_commands((x, y), best_cell))
x, y = best_cell
ops.append("C")
s_val ^= board_copy[x][y]
# boardのうち最も値が小さいところへ移動
smallest_cell = None
smallest_val = 10**9
for i in range(n):
for j in range(n):
if board_copy[i][j] < smallest_val:
smallest_val = board_copy[i][j]
smallest_cell = (i, j)
ops.extend(move_commands((x, y), smallest_cell))
x, y = smallest_cell
ops.append("C")
s_val ^= board_copy[x][y]
# s_valとboard_copy[x][y]を入れ替える
ops.append("W")
board_copy[x][y] ^= s_val
ops.append("C")
s_val ^= board_copy[x][y]
ops.append("W")
board_copy[x][y] ^= s_val
if len(ops) <= t:
return ops, calculate_score(board_copy)
else:
return [], 0
def main() -> None:
start_time = time.time()
n, t = map(int, sys.stdin.readline().split())
board_input = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
best_ops: List[str] = []
best_score = -1
trial_count = 0
# 時間制限内でランダム要素を入れた解法を試す
while time.time() - start_time < TIME_LIMIT:
board = [row[:] for row in board_input]
ops, score = solve_once(n, t, board)
trial_count += 1
if score > best_score:
best_ops = ops
best_score = score
# デバッグ情報（標準エラー出力）
print(f"Trials: {trial_count}, Best score: {best_score}", file=sys.stderr)
sys.stdout.write("\n".join(best_ops) + "\n")
if __name__ == "__main__":
main()