結果

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

ソースコード

diff # 

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 から A を構成（リストの長さを固定して高速化）"""
    A = [0] * (n + 1)
    A[0] = candidate[0]
    last_a = a[-1]
    mod_val = mod
    for i in range(n):
        A[i + 1] = (last_a[i] - A[i] + candidate[i + 1]) % mod_val
    return A

def score_from_candidate(candidate):
    """
    compute_A(candidate) に基づいて誤差（gosa）を計算。
    各段の誤差は abs(a[i][j] - computed_value) を mod を考慮して計算し、
    その最大値を返します（誤差が小さいほど良い）。
    """
    A = compute_A(candidate)
    mod_val = mod
    gosa = 0
    d = A
    # 下から上へ再帰的に計算（元のコードと同じ仕様）
    for i in range(n - 2, 0, -1):
        ai = a[i]  # 行 i の値をローカル参照
        ndp = [0] * i
        for j in range(i):
            s = d[j] + d[j - 1]
            x = s % mod_val
            ndp[j] = x
            # 誤差を mod を考慮して計算
            diff_val = x - ai[j]
            if diff_val < 0:
                diff_val = -diff_val
            # mod 周りの距離に直す
            diff_val = diff_val if diff_val < mod_val - diff_val else mod_val - diff_val
            if diff_val > gosa:
                gosa = diff_val
        d = ndp
    return gosa

# 初期候補解の生成（candidate[0]: 0～mod-1、candidate[1..n]: 計算で決定）
candidate = [randint(0, mod - 1)]
for i in range(n):
    candidate.append((a[-1][i] - candidate[-1]) % mod)
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 = time.time() - start
    T = T0 * ((T_end / T0) ** (t / TIME_LIMIT))
    
    new_candidate = candidate[:]  # candidate のコピー
    idx = randint(0, n)  # candidate のインデックスは 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] += delta
        if new_candidate[idx] < 0:
            new_candidate[idx] = 0
        elif new_candidate[idx] > 10:
            new_candidate[idx] = 10
    
    new_score = score_from_candidate(new_candidate)
    diff = new_score - current_score  # 誤差最小化なので、diff が正なら悪化
    # 改善（diff <= 0）の場合は必ず採用。劣化の場合は exp(-diff/T) の確率で採用。
    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