結果

問題 No.5021 Addition Pyramid
ユーザー あじゃじゃ
提出日時 2025-02-25 22:11:24
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,646 ms / 2,000 ms
コード長 2,393 bytes
コンパイル時間 435 ms
コンパイル使用メモリ 82,172 KB
実行使用メモリ 79,816 KB
スコア 2,530,100
最終ジャッジ日時 2025-02-25 22:13:32
合計ジャッジ時間 86,022 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

from random import randint
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):
    gosa=0
    for i in range(n):
      gosa=max(gosa,min(abs(a[-1][i]-candidate[i]),mod-abs(a[-1][i]-candidate[i])))
    return gosa

def score_from_candidate(candidate):
    """
    compute_A(candidate) に基づき、誤差（gosa）を計算する。
    各段における、計算値と入力値 a[i][j] との差（mod を考慮した絶対誤差）の最大値を返す。
    誤差が小さいほど良い解となる。
    """
    gosa = compute_A(candidate)
    d = candidate
    for i in range(n-2, 0, -1):
        ndp = []
        for j in range(i):
            x = (d[j] + d[j-1]) % mod
            ndp.append(x)
            g = abs(a[i][j] - x)
            err = g if g < mod - g else mod - g
            if err > gosa:
                gosa = err
        d = ndp
    return gosa

# 初期候補解の生成
# candidate[0] も candidate[1..n] も 0〜mod-1 のランダム整数
candidate = a[-1]
current_score = score_from_candidate(candidate)
best_score = current_score
best_candidate = candidate[:]
# 焼きなましのパラメータ
T0 = 1e5
T_end = 1e-3
TIME_LIMIT = 1.6

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-1)  # インデックスは 0～n（全 n+1 要素）
    if idx == 0:
        # 初期値は広い範囲で変更（-1000～1000）
        delta = randint(-1000, 1000)
        new_candidate[0] = (new_candidate[0] + delta) % mod
    else:
        # オフセットも 0〜mod-1 の範囲内で更新（-100～100）
        delta = randint(-100, 100)
        new_candidate[idx] = (new_candidate[idx] + delta) % mod
    
    new_score = score_from_candidate(new_candidate)
    diff = new_score - current_score  # 誤差最小化なので、diff < 0 が改善
    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[:]

print(*best_candidate)
0