結果

問題 No.5001 排他的論理和でランニング
ユーザー ra5anchor
提出日時 2025-04-27 12:27:11
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,424 ms / 1,500 ms
コード長 2,987 bytes
コンパイル時間 542 ms
コンパイル使用メモリ 82,296 KB
実行使用メモリ 194,540 KB
スコア 52,428,749
最終ジャッジ日時 2025-04-27 12:27:44
合計ジャッジ時間 30,485 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

import random
from time import perf_counter
import argparse
import sys

random.seed(0)

class TimeKeeper:
    def __init__(self):
        self.start_time = perf_counter()
    def is_time_over(self, LIMIT):
        return (perf_counter() - self.start_time) >= LIMIT
    def time_now(self):
        return (perf_counter() - self.start_time)

class XorSet:
    def __init__(self, initial):
        self.data = list(initial)
        self.pos  = {v:i for i,v in enumerate(self.data)}
        self.current_xor = 0
        for v in self.data:
            self.current_xor ^= v

    def __len__(self):
        return len(self.data)

    def random_element(self):
        return random.choice(self.data)
        # idx = random.randrange(len(self.data))
        # return self.data[idx]

    def remove(self, v):
        idx = self.pos[v]
        last = self.data[-1]
        self.data[idx] = last
        self.pos[last] = idx
        self.data.pop()
        del self.pos[v]
        self.current_xor ^= v

    def add(self, v):
        self.pos[v] = len(self.data)
        self.data.append(v)
        self.current_xor ^= v


def random_restart_hill_climbing(values, M, tk, LIMIT, no_improve_limit=1000):
    best_xor = -1
    best_data = None
    restart_count = 0

    # グローバルタイム管理の下で複数回ヒルクライミング
    while not tk.is_time_over(LIMIT):
        restart_count += 1
        # ランダム初期化
        random.shuffle(values)
        Sa = XorSet(values[:M])
        Sb = XorSet(values[M:])
        current_xor = Sa.current_xor
        no_improve = 0
        last_improve = 0

        # 局所探索
        while no_improve < no_improve_limit and not tk.is_time_over(LIMIT):
            a_val = Sa.random_element()
            b_val = Sb.random_element()
            new_xor = current_xor ^ a_val ^ b_val
            if new_xor > current_xor:
                Sa.remove(a_val)
                Sb.remove(b_val)
                Sa.add(b_val)
                Sb.add(a_val)
                current_xor = new_xor
                last_improve = no_improve
                no_improve = 0
            else:
                no_improve += 1

        # 局所解比較
        if current_xor > best_xor:
            best_xor = current_xor
            best_data = list(Sa.data)
            print(f"Restart {restart_count}: new best_xor = {best_xor} {last_improve=}", file=sys.stderr)
            if best_xor == 1048575:
                break

    return best_data, best_xor


def main(DEBUG):
    parser = argparse.ArgumentParser()
    parser.add_argument('--debug', action='store_true')
    args = parser.parse_args()

    tk = TimeKeeper()
    LIMIT = 1.3

    N, M = map(int, input().split())
    A = list(map(int, input().split()))

    best_data, best = random_restart_hill_climbing(A, M, tk, LIMIT, no_improve_limit=100000)

    # 出力
    print(*best_data)
    print("SC", best, tk.time_now(), file=sys.stderr)

if __name__ == '__main__':
    main(False)
0