結果
問題 | No.5020 Averaging |
ユーザー |
|
提出日時 | 2025-01-25 19:44:44 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 936 ms / 1,000 ms |
コード長 | 5,645 bytes |
コンパイル時間 | 2,023 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 78,680 KB |
スコア | 82,663,549 |
最終ジャッジ日時 | 2025-01-25 19:45:37 |
合計ジャッジ時間 | 50,827 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 50 |
ソースコード
import randomimport mathfrom time import perf_counterimport sysimport itertoolstry:import matplotlib.pyplot as pltUSE_PLOT = Trueexcept ImportError:# matplotlib が無い環境ではグラフ表示をしないUSE_PLOT = Falseclass TimeKeeper:def __init__(self):self.start_time = perf_counter()def is_time_over(self, LIMIT):return (perf_counter() - self.start_time) >= LIMITdef time_now(self):return (perf_counter() - self.start_time)# 定数とグローバル変数TARGET = 500000000000000000N = 0A = []B = []Order = []BestOrder = []def get_score():"""現在の Order 順に従い V1, V2 を計算し、最後に max(|TARGET - V1|, |TARGET - V2|) を返す。"""V1, V2 = A[0], B[0]for i in range(N - 1):V1 = (V1 + A[Order[i]]) // 2V2 = (V2 + B[Order[i]]) // 2return max(abs(TARGET - V1), abs(TARGET - V2))def get_score2(First, Last):V1 = dict()V2 = dict()V1[0] = A[0]V2[0] = B[0]for id in First:if id not in V1:V1[id] = A[id]V2[id] = B[id]for id in First:v1 = (V1[0] + V1[id]) // 2v2 = (V2[0] + V2[id]) // 2V1[0] = v1V1[id] = v1V2[0] = v2V2[id] = v2for i in range(len(Last)):V1[0] = (V1[0] + A[Last[i]]) // 2V2[0] = (V2[0] + B[Last[i]]) // 2return max(abs(TARGET - V1[0]), abs(TARGET - V2[0]))def main():global N, A, B, Order, BestOrder# 乱数シードを固定random.seed(0)tk = TimeKeeper()LIMIT = 0.85# 入力N = int(input()) # N=45固定A = [0] * NB = [0] * Nfor i in range(N):A[i], B[i] = map(int, input().split())# 初期化Order = list(range(1, N))current_score = get_score()best_score = current_score# --- ログ用リスト ---# (iteration, best_score, current_score, elapsed_time) を保存if USE_PLOT == True:score_history = []score_history.append((0, best_score, current_score, tk.time_now()))# ---- 焼きなましパラメータ ----loop = 0T0, T1 = 0.2, 0.2T = T0while True:loop += 1# 一定ループごとに温度を更新 + タイムオーバー判定if loop % 1000 == 0:T = T0 + (T1 - T0) * tk.time_now() / LIMITif tk.is_time_over(LIMIT):break# 1000ループごとにログに追加 (ベストスコアの推移を確認)if USE_PLOT == True:score_history.append((loop, best_score, current_score, tk.time_now()))# ランダムスワップidx1 = random.randrange(N - 1)idx2 = random.randrange(N - 1)Order[idx1], Order[idx2] = Order[idx2], Order[idx1]# スコア計算cand_score = get_score()diff = math.log10(current_score) - math.log10(cand_score)# メトロポリス判定if random.random() < math.exp(diff / T):# 採用if best_score > cand_score:best_score = cand_scoreBestOrder = Order[:]current_score = cand_scoreelse:# 不採用なら元に戻すOrder[idx1], Order[idx2] = Order[idx2], Order[idx1]# 探索終了後に最終的な値も記録if USE_PLOT == True:score_history.append((loop, best_score, current_score, tk.time_now()))print("Yaki", best_score, file=sys.stderr)# 改善L1 = BestOrder[:4]L2 = BestOrder[4:]for k in range(1, 11):for first in itertools.combinations_with_replacement(L1, k):sc = get_score2(list(first), L2)# print(sc, file=sys.stderr)if sc < best_score:print('BEST!', file=sys.stderr)best_score = scBestOrder = list(first) + L2# 探索終了後に最終的な値も記録if USE_PLOT == True:score_history.append((loop, best_score, current_score, tk.time_now()))print("Final", best_score, file=sys.stderr)# 結果出力 (提出フォーマットに応じて調整)M = len(BestOrder)ANS = [(1, BestOrder[i] + 1) for i in range(M)]print(len(ANS))for a in ANS:print(a[0], a[1])sc = int(2*10**6 - 10**5 * math.log10(best_score + 1))print(sc, best_score, loop, file=sys.stderr)# ---------------------# ログの可視化# ---------------------if USE_PLOT:# matplotlib が利用できる場合にグラフ化loops = [h[0] for h in score_history]best_scores = [h[1] for h in score_history]curr_scores = [h[2] for h in score_history]times = [h[3] for h in score_history]fig, ax1 = plt.subplots()ax1.set_xlabel('Iteration')ax1.set_ylabel('Score (log scale)')# ログスケールをとるために log10(スコア+1) で表示ax1.plot(loops, [math.log10(bs+1) for bs in best_scores],label='Best Score (log10)', color='blue')ax1.plot(loops, [math.log10(cs+1) for cs in curr_scores],label='Current Score (log10)', color='red', alpha=0.5)ax1.legend(loc='upper right')ax1.set_title('Annealing Score Transition')# 時間との関係を見る場合には別の軸を用意しても良い# 例: ax2 = ax1.twinx() などplt.show()# plt.savefig('score_history.png') # ファイルに保存も可能if __name__ == "__main__":main()