結果

問題 No.5021 Addition Pyramid
ユーザー あじゃじゃ
提出日時 2025-02-25 21:44:33
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,645 ms / 2,000 ms
コード長 2,631 bytes
コンパイル時間 630 ms
コンパイル使用メモリ 82,184 KB
実行使用メモリ 79,952 KB
スコア 1,658,026
最終ジャッジ日時 2025-02-25 21:46:00
合計ジャッジ時間 86,333 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge4
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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):
    """
    candidate[0] : 最初の値（0〜mod-1）
    candidate[1..n] : 各段に加えるオフセット（0〜mod-1）
    与えた 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) に基づき、誤差（gosa）を計算する。
    各段における、計算値と入力値 a[i][j] との差（mod を考慮した絶対誤差）の最大値を返す。
    誤差が小さいほど良い解となる。
    """
    A = compute_A(candidate)
    gosa = 0
    d = A
    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 = [randint(0, mod-1)] + [randint(0, mod-1) 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.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)  # インデックスは 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(*compute_A(best_candidate))
0