結果

問題 No.5022 XOR Printer
コンテスト
ユーザー ぬるぽ
提出日時 2025-07-26 13:54:15
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,974 ms / 2,000 ms
コード長 6,432 bytes
コンパイル時間 457 ms
コンパイル使用メモリ 82,052 KB
実行使用メモリ 96,864 KB
スコア 4,926,888,075
最終ジャッジ日時 2025-07-26 13:56:05
合計ジャッジ時間 98,611 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

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)


#!/usr/bin/env python3
"""
Greedy XOR solver (v5)  ―  a は「現在値の小さい上位 K=5 個」だけ試す版
---------------------------------------------------------------------------
* 1 手番で Copy×1 または Copy×2 を選び、gain / cost を最大化。
* a 候補は「まだ試していないセルのうち値が小さい順に 5 個」だけ。
* グリッドが大きくても毎ラウンド O(K·N² + K·B + K·B²) 程度で済む:
      ‑ a 探索     : 1 回スキャンで上位 K (=5) を抽出
      ‑ 1‑copy探索 : K × B
      ‑ 2‑copy探索 : K × B²
  (B = N² = 100 なら 5×10 000 ≒ 5e4 試行で十分高速)
* 手数上限 T=1000、1 改善あたり使える手数は MAX_COST=10。
"""

import sys
from heapq import nsmallest
from itertools import product


# ───────────────────────── helpers ──────────────────────────
def manh(r1, c1, r2, c2):
    return abs(r1 - r2) + abs(c1 - c2)


def moves(r1, c1, r2, c2):
    s = []
    if r2 > r1:
        s.extend("D" * (r2 - r1))
    else:
        s.extend("U" * (r1 - r2))
    if c2 > c1:
        s.extend("R" * (c2 - c1))
    else:
        s.extend("L" * (c1 - c2))
    return s


# ─────────────────────────── main ───────────────────────────
def main() -> None:
    N, T = map(int, sys.stdin.readline().split())
    A = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

    coords = [(i, j) for i in range(N) for j in range(N)]  # 全セル
    r = c = 0  # 現位置
    s = 0  # レジスタ
    ops = []  # 出力操作列
    step = 1  # ログ用
    MAX_COST = 30  # 1 改善に費やす手数上限
    K = 5  # a 候補数

    while True:
        # ───────── K 個の最小セルを取得 ─────────
        k_small = nsmallest(K, coords, key=lambda rc: A[rc[0]][rc[1]])

        best = None  # (ratio, gain, cost, plan)

        # ───────── 各 a について探索 ──────────
        for ar, ac in k_small:
            a_val = A[ar][ac]

            # 1‑copy  -------------------------------------------------------
            for br, bc in coords:
                if (br, bc) == (ar, ac):
                    continue
                cost = manh(r, c, br, bc) + 1 + manh(br, bc, ar, ac) + 1
                if cost > MAX_COST or len(ops) + cost > T:
                    continue
                new_val = a_val ^ (s ^ A[br][bc])
                gain = new_val - a_val
                if gain <= 0:
                    continue
                ratio = gain / cost
                if best is None or ratio > best[0]:
                    best = (ratio, gain, cost, ("1", ar, ac, br, bc))

            # 2‑copy  -------------------------------------------------------
            for (b1r, b1c), (b2r, b2c) in product(coords, repeat=2):
                if (b1r, b1c) == (ar, ac) or (b2r, b2c) == (ar, ac):
                    continue
                cost = (
                    manh(r, c, b1r, b1c)
                    + 1
                    + manh(b1r, b1c, b2r, b2c)
                    + 1
                    + manh(b2r, b2c, ar, ac)
                    + 1
                )
                if cost > MAX_COST or len(ops) + cost > T:
                    continue
                new_val = a_val ^ (s ^ A[b1r][b1c] ^ A[b2r][b2c])
                gain = new_val - a_val
                if gain <= 0:
                    continue
                ratio = gain / cost
                if best is None or ratio > best[0]:
                    best = (ratio, gain, cost, ("2", ar, ac, b1r, b1c, b2r, b2c))

        # ───────── 実行 or 終了 ──────────
        if best is None:
            break  # 改善候補なし

        ratio, gain, cost, plan = best
        if plan[0] == "1":
            _, ar, ac, br, bc = plan
            vb = A[br][bc]

            print(
                f"Step {step}: 1‑copy "
                f"a=({ar+1},{ac+1}) val={A[ar][ac]} | "
                f"b=({br+1},{bc+1}) val={vb} | "
                f"s={s} | gain={gain}/cost={cost:.1f}",
                file=sys.stderr,
            )

            ops.extend(moves(r, c, br, bc))
            ops.append("C")
            s ^= vb
            r, c = br, bc

            ops.extend(moves(r, c, ar, ac))
            ops.append("W")
            old = A[ar][ac]
            A[ar][ac] ^= s
            r, c = ar, ac

            print(f"        A[{ar+1},{ac+1}]: {old} -> {A[ar][ac]} | new s={s}", file=sys.stderr)

        else:  # 2‑copy
            _, ar, ac, b1r, b1c, b2r, b2c = plan
            vb1, vb2 = A[b1r][b1c], A[b2r][b2c]

            print(
                f"Step {step}: 2‑copy "
                f"a=({ar+1},{ac+1}) val={A[ar][ac]} | "
                f"b1=({b1r+1},{b1c+1}) val={vb1} | "
                f"b2=({b2r+1},{b2c+1}) val={vb2} | "
                f"s={s} | gain={gain}/cost={cost:.1f}",
                file=sys.stderr,
            )

            ops.extend(moves(r, c, b1r, b1c))
            ops.append("C")
            s ^= vb1
            r, c = b1r, b1c

            ops.extend(moves(r, c, b2r, b2c))
            ops.append("C")
            s ^= vb2
            r, c = b2r, b2c

            ops.extend(moves(r, c, ar, ac))
            ops.append("W")
            old = A[ar][ac]
            A[ar][ac] ^= s
            r, c = ar, ac

            print(f"        A[{ar+1},{ac+1}]: {old} -> {A[ar][ac]} | new s={s}", file=sys.stderr)

        step += 1

    # ───────── 終了処理 ──────────
    total = sum(map(sum, A))
    print(f"Final score: {total}", file=sys.stderr)
    print("\n".join(ops))


if __name__ == "__main__":
    main()
0