結果

問題 No.5021 Addition Pyramid
コンテスト
ユーザー brthyyjp
提出日時 2025-02-25 22:01:06
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 74 ms / 2,000 ms
コード長 2,646 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 549 ms
コンパイル使用メモリ 82,552 KB
実行使用メモリ 72,548 KB
スコア 3,431,729
最終ジャッジ日時 2025-02-25 22:01:12
合計ジャッジ時間 6,266 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
import time

def solve():
    MOD = 10**8
    
    # 1. 入力読み取り
    N = int(input())  # 問題文では N=50 の想定
    a = []
    for i in range(N):
        row = list(map(int, input().split()))
        a.append(row)
    
    # 2. 最下段 c を a_{N-1,*} (1-index的には a_{N,*}) で初期化
    #    Pythonの配列では a[N-1] が最下段に対応
    c = a[N-1][:]  # 長さNのリスト
    
    # ピラミッド構築 (下から上へ)
    def build_pyramid(c_list):
        # b[i] : 上から i+1 段目 (0-indexで i=0 が最上段)
        # ただし問題文と i の定義が逆転している点に注意
        # ここでは下から作りたいので b[N-1] = c_list
        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):
        # a_pyr[i][j], b_pyr[i][j] で i=0が最上段
        # 距離 = min(|a-b|, MOD - |a-b|)
        # これの最大値を返す
        diff_max = 0
        for i in range(N):
            for j in range(i+1):
                d = abs(a_pyr[i][j] - b_pyr[i][j])
                if d > MOD//2:
                    d = MOD - d
                if d > diff_max:
                    diff_max = d
        return diff_max
    
    # 初期のピラミッドを構築し，誤差を計算
    b = build_pyramid(c)
    bestX = max_cycle_dist(a, b)
    
    start_time = time.time()
    
    # 3. 局所探索: c_j を ±1 ずつ試して改善するかチェック
    for j in range(N):
        # 時間チェック
        if time.time() - start_time > 1.8:
            break
        
        original = c[j]
        
        # +1 を試す
        c[j] = (original + 1) % MOD
        b_test = build_pyramid(c)
        newX = max_cycle_dist(a, b_test)
        if newX < bestX:
            # 改善するなら採用
            bestX = newX
        else:
            # 戻す
            c[j] = original
        
        # 時間チェック
        if time.time() - start_time > 1.8:
            break
        
        # -1 を試す
        original2 = c[j]
        c[j] = (original - 1) % MOD
        b_test = build_pyramid(c)
        newX = max_cycle_dist(a, b_test)
        if newX < bestX:
            bestX = newX
        else:
            c[j] = original2
    
    # 4. 結果を出力
    print(" ".join(map(str, c)))


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