結果

問題 No.5001 排他的論理和でランニング
ユーザー ra5anchor
提出日時 2025-04-19 13:27:07
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,317 ms / 1,500 ms
コード長 4,073 bytes
コンパイル時間 586 ms
コンパイル使用メモリ 82,788 KB
実行使用メモリ 99,800 KB
スコア 52,428,727
最終ジャッジ日時 2025-04-19 13:28:18
合計ジャッジ時間 70,679 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

import copy
import random
from time import perf_counter
import argparse
import sys
import math

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):
        # リスト＋辞書で要素集合を管理し、
        # 定数時間でランダム選択・追加・削除・XOR 更新を行う
        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):
        idx = random.randrange(len(self.data))
        return self.data[idx]

    def remove(self, v):
        idx = self.pos[v]
        last = self.data[-1]
        # スワップして末尾を pop
        self.data[idx] = last
        self.pos[last] = idx
        self.data.pop()
        del self.pos[v]
        # XOR 更新
        self.current_xor ^= v

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

def hill_climbing_xor(values, M, tk, LIMIT):
    # 初期分割
    random.shuffle(values)
    Sa = XorSet(values[:M])
    Sb = XorSet(values[M:])
    best_xor = Sa.current_xor

    loop = 0
    while True:
        loop += 1
        if loop%100==0 and tk.is_time_over(LIMIT):
            break

        # 近傍：A から a_val, Sb から b_val をランダムに選んで交換を試す
        a_val = Sa.random_element()
        b_val = Sb.random_element()

        # 交換後の Sa の XOR を定数時間で計算
        new_xor = Sa.current_xor ^ a_val ^ b_val

        # 改善があれば実際にスワップ
        if new_xor > Sa.current_xor:
            Sa.remove(a_val)
            Sb.remove(b_val)
            Sa.add(b_val)
            Sb.add(a_val)
            best_xor = new_xor
            print(f"best: {loop=} {best_xor=}", file=sys.stderr)

    return Sa, Sb, best_xor


def simulated_annealing_xor(values, M, tk, LIMIT):
    # 初期分割
    random.shuffle(values)
    Sa = XorSet(values[:M])
    Sb = XorSet(values[M:])
    best_xor = Sa.current_xor

    # 温度スケジュールパラメータ
    T0 = max(values)
    T_final = 1e-3

    while not tk.is_time_over(LIMIT):
        t = tk.time_now()
        # 幾何学的減衰による温度更新
        T = T0 * math.exp((math.log(T_final/T0) * t) / LIMIT)
        # 線形減衰を使う場合:
        # T = T0 - (T0 - T_final) * (t / LIMIT)

        a_val = Sa.random_element()
        b_val = Sb.random_element()
        new_xor = Sa.current_xor ^ a_val ^ b_val
        delta = new_xor - Sa.current_xor

        # 改善または確率的受容
        if delta > 0 or random.random() < math.exp(delta / T):
            Sa.remove(a_val)
            Sb.remove(b_val)
            Sa.add(b_val)
            Sb.add(a_val)
            # ベスト更新
            if Sa.current_xor > best_xor:
                best_xor = Sa.current_xor
                print(f"New best at t={t:.4f}s: {best_xor}", file=sys.stderr)

    return Sa, Sb, best_xor


###########################################
def main(DEBUG):
    tk = TimeKeeper()
    LIMIT = 1.2

    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    # 5 <= N <= 10**5
    # 1 <= M <= N
    # 1 <= Ai <= 10**6
    # Ai != Aj
    # print(M, file=sys.stderr)
    # exit()

    # Sa, Sb, best = hill_climbing_xor(A, M, tk, LIMIT)
    Sa, Sb, best = simulated_annealing_xor(A, M, tk, LIMIT)

    print(*Sa.data)
    print("SC", best, file=sys.stderr)    
    return
    

if __name__ == '__main__':
    parser = argparse.ArgumentParser(description='Debug mode')
    parser.add_argument('--debug', action='store_true', help='Enable debug mode')
    args = parser.parse_args()
    main(args.debug)
0