結果
| 問題 |
No.5022 XOR Printer
|
| ユーザー |
 ぬるぽ
|
| 提出日時 | 2025-07-26 13:40:19 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 77 ms / 2,000 ms |
| コード長 | 7,355 bytes |
| コンパイル時間 | 599 ms |
| コンパイル使用メモリ | 82,288 KB |
| 実行使用メモリ | 73,676 KB |
| スコア | 2,648,145,733 |
| 最終ジャッジ日時 | 2025-07-26 13:40:26 |
| 合計ジャッジ時間 | 6,730 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge6 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
import heapq
import io
import math
import sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from copy import copy
from functools import lru_cache
from itertools import accumulate, combinations, groupby, permutations
# from atcoder.lazysegtree import LazySegTree
# from atcoder.dsu import DSU
# from sortedcontainers import SortedList
# import pypyjit
# pypyjit.set_param("max_unroll_recursion=-1")
sys.setrecursionlimit(10**9)
_INPUT = """\
10 1000
264226 49169 452706 349656 591257 939313 965593 871829 573328 196338
291143 313614 102898 339417 420594 203975 651471 212732 822702 685313
862005 943317 611335 528205 455991 262616 867703 1028391 703524 860993
896676 271690 561040 450129 826813 876431 694071 293171 891887 693806
626044 607180 1016324 968104 385080 868049 429686 77054 453275 151375
750591 902239 318944 900896 433106 111074 167011 340127 457484 272259
378544 525816 49128 59276 190577 1039936 837310 360131 94834 183359
50293 762494 90250 538119 176582 826349 842467 1015725 320518 472303
262810 116152 723885 476803 17080 635800 651935 471616 126811 14611
563997 595247 651881 576124 735175 681983 523995 975381 542258 362094
"""
sys.stdin = io.StringIO(_INPUT)
# https://github.com/tatyam-prime/SortedSet/blob/main/SortedMultiset.py
import math
#!/usr/bin/env python3
# Greedy solver for the XOR‑copy/write AHC sample
# - Grid size : N = 10
# - Move limit: T = 1000
#
# Strategy
# --------
# Repeatedly:
# 1. Find the cell with the current minimum value (call it *a*).
# 2. Among all cells (*b*), choose the one that maximises the value
# that *a* will take after the sequence “C on *b* → W on *a*”.
# After copying we have s_new = s_old XOR A[b]
# and the write yields A[a] ← A[a] XOR s_new
# 3. If this best value is not larger than A[a], stop.
# 4. Otherwise emit the path:
# pos → b : moves, C
# b → a : moves, W
# updating `s`, `A`, `pos`, and the remaining budget.
#
# The search stops when no improvement is possible or the next sequence
# would exceed the remaining move budget (≤ T).
#!/usr/bin/env python3
"""
Greedy solver for the XOR‑copy/write AHC problem.
Algorithm
---------
1. While we still have move budget (T) left:
1. Find cell (ar, ac) with the minimal current value `a = A[ar][ac]`.
2. Pick cell (br, bc) whose value `b = A[br][bc]` maximises
new_val = a XOR (s XOR b) .
(Because `C` on (br,bc) makes `s ← s XOR b`,
then `W` on (ar,ac) makes `A[ar][ac] ← a XOR s`.)
3. If `new_val` ≤ a, stop (no more improvement).
4. If the full sequence “move→C→move→W” would exceed `T`, stop.
5. Otherwise emit:
path(pos → (br,bc)) + 'C'
path((br,bc) → (ar,ac)) + 'W'
updating `s`, `A`, position, and remaining budget.
"""
import sys
#!/usr/bin/env python3
"""
Greedy XOR solver with verbose logging on stderr.
Logging details
---------------
* Each successful step prints to **stderr**:
Step k: a=(ra,ca) val=old_a | b=(rb,cb) val=b | s=old_s
A[ra,ca] : old_a -> new_a | new s=updated_s
(coordinates are 1‑indexed)
* After the loop finishes, the final grid sum S is printed to **stderr**.
* Only the operation sequence (one char per line) is sent to stdout,
so the judge sees the correct answer format.
"""
import sys
#!/usr/bin/env python3
"""
Greedy XOR solver (v2)
----------------------
* 最小値セル a を小さい順に試し，
・a XOR (s XOR b) > a となる b が見つかれば即実行
・見つからなければ “次に小さい a” を試す
* そのループ内で 1 回も改善できなければ終了
* 操作列は stdout，詳細ログは stderr
"""
import sys
def path_moves(r1, c1, r2, c2):
seq = []
if r2 > r1:
seq.extend("D" * (r2 - r1))
else:
seq.extend("U" * (r1 - r2))
if c2 > c1:
seq.extend("R" * (c2 - c1))
else:
seq.extend("L" * (c1 - c2))
return seq
def manhattan(r1, c1, r2, c2):
return abs(r1 - r2) + abs(c1 - c2)
# ────────────────────────── main ───────────────────────────
def main() -> None:
N, T = map(int, sys.stdin.readline().split())
A = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
r = c = 0 # 現在位置 (0‑indexed)
s = 0 # レジスタ
ops = [] # 出力操作列
step = 1 # ログ用カウンタ
while True:
# ── そのループで改善できたか ──
improved_this_round = False
tried = [[False] * N for _ in range(N)] # 今ラウンドで既に試したか
while True:
# 1) 「まだ試していない」セルのうち最小のものを探す
a_val = None
for i in range(N):
for j in range(N):
if tried[i][j]:
continue
if a_val is None or A[i][j] < a_val:
a_val = A[i][j]
ar, ac = i, j
if a_val is None:
break # 全セル試しても改善なし → 外側 while を抜ける
tried[ar][ac] = True # この a は試した
# 2) 今の a について最良の b を探す
best_val = a_val
br = bc = -1
for i in range(N):
for j in range(N):
cand = a_val ^ (s ^ A[i][j])
if cand > best_val:
best_val = cand
br, bc = i, j
if br == -1:
continue # この a は改善不可 → 次に小さい a を探す
# 3) 手数チェック
need = manhattan(r, c, br, bc) + 1 + manhattan(br, bc, ar, ac) + 1
if len(ops) + need > T:
print("手数不足で終了", file=sys.stderr)
tried = None # ループ外で break させる
break
# 4) ログ (stderr)
print(
f"Step {step}: a=({ar+1},{ac+1}) val={a_val} | "
f"b=({br+1},{bc+1}) val={A[br][bc]} | s={s}",
file=sys.stderr,
)
# 5) 実際に移動 + C
ops.extend(path_moves(r, c, br, bc))
ops.append("C")
s ^= A[br][bc]
r, c = br, bc
# 6) 移動 + W
ops.extend(path_moves(r, c, ar, ac))
ops.append("W")
old_a = A[ar][ac]
A[ar][ac] ^= s
r, c = ar, ac
print(
f" A[{ar+1},{ac+1}]: {old_a} -> {A[ar][ac]} | new s={s}",
file=sys.stderr,
)
step += 1
improved_this_round = True
break # s が変わったので新たに a を探す
if not improved_this_round:
break # 1 ラウンド何も改善できなかった
if tried is None: # 手数不足 break
break
# ── 総スコア ──
total = sum(sum(row) for row in A)
print(f"Final score: {total}", file=sys.stderr)
# ── 操作列出力 ──
print("\n".join(ops))
if __name__ == "__main__":
main()