結果

問題 No.5021 Addition Pyramid
コンテスト
ユーザー brthyyjp
提出日時 2025-02-25 22:27:18
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,882 ms / 2,000 ms
コード長 3,295 bytes
コンパイル時間 470 ms
コンパイル使用メモリ 82,364 KB
実行使用メモリ 80,860 KB
スコア 4,705,959
最終ジャッジ日時 2025-02-25 22:28:56
合計ジャッジ時間 97,192 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import time
import math
import random

def solve():
    input_data = sys.stdin.read().strip().split()
    MOD = 10**8
    
    # 1. 入力読み取り
    N = int(input_data[0])  # N=50
    a = []
    idx = 1
    for i in range(N):
        row = list(map(int, input_data[idx:idx + (i+1)]))
        a.append(row)
        idx += (i+1)
    
    # 2. 初期解 c: 最下段を a[N-1] と同じに
    c = a[N-1][:]  # a[N-1] は長さN
    
    # ピラミッド構築
    def build_pyramid(c_list):
        # b[i] は上から i段目(0-index)。b[0] が最上段、b[N-1] が最下段
        b = [[0]*(i+1) for i in range(N)]
        b[N-1] = c_list[:]  # コピー
        
        for i in reversed(range(N-1)):
            for j in range(i+1):
                b[i][j] = (b[i+1][j] + b[i+1][j+1]) % MOD
        return b
    
    # 最大サイクル距離(問題指定の誤差)を計算
    def max_cycle_dist(a_pyr, b_pyr):
        diff_max = 0
        for i in range(N):
            for j in range(i+1):
                d = abs(a_pyr[i][j] - b_pyr[i][j])
                # mod 1e8 での距離
                if d > MOD // 2:
                    d = MOD - d
                if d > diff_max:
                    diff_max = d
        return diff_max
    
    # コスト(= 最大誤差)を計算する関数
    def calc_cost(c_list):
        b_pyramid = build_pyramid(c_list)
        return max_cycle_dist(a, b_pyramid)
    
    # 初期解のコスト
    current_cost = calc_cost(c)
    best_c = c[:]
    best_cost = current_cost
    
    # 焼きなまし用パラメータ
    T = 100.0          # 初期温度(調整パラメータ)
    COOL = 0.995       # 温度減衰率(調整パラメータ)
    
    start_time = time.time()
    
    # 3. 焼きなましループ
    while True:
        # 時間制限チェック
        if time.time() - start_time > 1.8:
            break
        
        # ランダムに 1箇所 選んで ±1 する (近傍操作)
        j = random.randint(0, N-1)
        old_val = c[j]
        
        # ±1 のどちらかをランダムに
        delta = 1 if (random.random() < 0.5) else -1
        c[j] = (c[j] + delta) % MOD
        
        # 新コストを計算
        new_cost = calc_cost(c)
        
        # 変化量 (SAでは"コストは小さい方が良い"ので old-new)
        diff = current_cost - new_cost
        
        if diff > 0:
            # 改善なら常に採用
            current_cost = new_cost
            if new_cost < best_cost:
                best_cost = new_cost
                best_c = c[:]
        else:
            # 悪化する場合は確率的に採用
            # (diff が負なので -diff は正数)
            p = math.exp(diff / T)  # diff < 0 なので 0 < p < 1
            if random.random() < p:
                # 採用
                current_cost = new_cost
                if new_cost < best_cost:
                    best_cost = new_cost
                    best_c = c[:]
            else:
                # 棄却: 元に戻す
                c[j] = old_val
        
        # 温度を下げる
        T *= COOL
    
    # 4. 結果出力 (最良解)
    print(" ".join(map(str, best_c)))


if __name__ == "__main__":
    sys.setrecursionlimit(10**7)
    solve()
0