結果

問題 No.5022 XOR Printer
ユーザー prussian_coder
提出日時 2025-07-23 16:35:41
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,778 ms / 2,000 ms
コード長 6,213 bytes
コンパイル時間 398 ms
コンパイル使用メモリ 82,444 KB
実行使用メモリ 92,184 KB
スコア 5,204,845,065
最終ジャッジ日時 2025-07-26 12:43:33
合計ジャッジ時間 92,491 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

# https://yukicoder.me/submissions/1106512の回る順番を局所探索ベースに変える
# あるbitに対して、そのbitが0であるセルを全て回るような経路をローカルサーチベースで求める
# 時間いっぱい繰り返して、その中で最もスコアが高いものを選ぶ


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]

    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) >= t:
            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 > t:
            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) > t:
            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) >= t:
                break
            if (x, y) != cell:
                path = move_commands((x, y), cell)
                if len(ops) + len(path) > t:
                    break
                ops.extend(path)
                x, y = cell
            if board_copy[x][y] ^ s_val > board_copy[x][y] and len(ops) < t:
                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]

    score = calculate_score(board_copy)
    return ops, score


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()
0