結果
問題 |
No.5021 Addition Pyramid
|
ユーザー |
![]() |
提出日時 | 2025-02-25 21:21:28 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,248 ms / 2,000 ms |
コード長 | 2,571 bytes |
コンパイル時間 | 250 ms |
コンパイル使用メモリ | 82,316 KB |
実行使用メモリ | 79,588 KB |
スコア | 1,925,336 |
最終ジャッジ日時 | 2025-02-25 21:22:34 |
合計ジャッジ時間 | 66,043 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 50 |
ソースコード
from random import randint, choice import math import time import random start = time.time() n = int(input()) a = [list(map(int, input().split())) for _ in range(n)] mod = 10**8 def compute_A(candidate): """ candidate[0] : 最初の値(0〜mod-1) candidate[1..n] : 各段に加えるオフセット(0〜10) 与えた candidate から A を構成する。 """ A = [candidate[0]] for i in range(n): A.append((a[-1][i] - A[-1] + candidate[i+1]) % mod) return A def score_from_candidate(candidate): """ compute_A(candidate) に基づき、score(ここでは gosa として定義) を計算する。元のコードは誤差を小さくする(minimize)目的でしたが、 今回はこれを最大化するように探索します。 """ A = compute_A(candidate) gosa = 0 d = A for i in range(n-2, 0, -1): ndp = [] for j in range(i): ndp.append((d[j] + d[j-1]) % mod) g = abs(a[i][j] - ndp[-1]) gosa = max(gosa, min(g, mod - g)) d = ndp return gosa # 初期候補解の生成 # candidate[0] は 0〜mod-1 のランダム整数、candidate[1..n] は 0〜10 のランダム整数 candidate = [randint(0, mod-1)] + [randint(0, 10) for _ in range(n)] current_score = score_from_candidate(candidate) best_score = current_score best_candidate = candidate[:] # 焼きなましのパラメータ(時間・温度スケジュールは適宜調整してください) T0 = 1e5 T_end = 1e-3 TIME_LIMIT = 1.2 while time.time() - start < TIME_LIMIT: t_elapsed = time.time() - start # 温度は経過時間に応じて指数的に下げる T = T0 * ((T_end / T0) ** (t_elapsed / TIME_LIMIT)) new_candidate = candidate[:] idx = randint(0, n) if idx == 0: delta = randint(-1000, 1000) new_candidate[0] = (new_candidate[0] + delta) % mod else: delta = choice([-1, 1]) new_candidate[idx] = new_candidate[idx] + delta if new_candidate[idx] < 0: new_candidate[idx] = 0 if new_candidate[idx] > 10: new_candidate[idx] = 10 new_score = score_from_candidate(new_candidate) diff = new_score - current_score if diff >= 0 or random.random() < math.exp(diff / T): candidate = new_candidate current_score = new_score if new_score > best_score: best_score = new_score best_candidate = new_candidate[:] # 最終的な A の値を出力 print(*compute_A(best_candidate))