結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

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[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))
0