結果

問題 No.5021 Addition Pyramid
コンテスト
ユーザー brthyyjp
提出日時 2025-02-25 23:08:15
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 129 ms / 2,000 ms
コード長 3,610 bytes
コンパイル時間 574 ms
コンパイル使用メモリ 82,428 KB
実行使用メモリ 78,112 KB
スコア 2,004,118
最終ジャッジ日時 2025-02-25 23:08:24
合計ジャッジ時間 8,212 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge2
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

#!/usr/bin/env python3
mod = 10**8

def error(x, y):
    """ x と y の誤差（循環距離：|x-y| と mod - |x-y| の小さい方） """
    diff = abs(x - y)
    return min(diff, mod - diff)

def compute_row(prev_row, pivot_index, pivot_val):
    """
    prev_row: 上段の値（長さ n のリスト）
    pivot_index: 新たな行（長さ n+1）の自由変数とするセルのインデックス (0-indexed)
    pivot_val: そのセルに設定する値
    新たな行 new_row を，右側： new_row[j+1] = (prev_row[j] - new_row[j]) mod mod，
    左側： new_row[j-1] = (prev_row[j-1] - new_row[j]) mod mod
    により決定する．
    """
    n = len(prev_row)
    L = n + 1
    new_row = [None] * L
    new_row[pivot_index] = pivot_val
    # 右側を決定
    for j in range(pivot_index, L - 1):
        new_row[j + 1] = (prev_row[j] - new_row[j]) % mod
    # 左側を決定
    for j in range(pivot_index, 0, -1):
        new_row[j - 1] = (prev_row[j - 1] - new_row[j]) % mod
    return new_row

def beam_search(a, beam_width=10, delta_range=5):
    """
    a: 目標ピラミッド（各段の値 a[i][j]，0-indexed．第0段は1要素，...，第N-1段は N 要素）
    beam_width: 各段で保持する候補数
    delta_range: 自由変数（中央のセル）の候補として，ターゲット値からのずれ [-delta_range, delta_range] を試す
    ビームサーチで各段を決定し，最終的な底辺（最下段の候補）を返す．
    各段における候補の評価は，その段での各セルの誤差（error 関数）
    とこれまでの最大誤差の最大値を用いる（最小化したい）。
    """
    N = len(a)
    # beam の各候補は (current_row, current_max_error) のタプル．
    # 最上段は確定： [a[0][0]] で誤差は 0 とする．
    beam = [ ([a[0][0]], 0) ]
    # 1段目から下段へ拡張していく
    for i in range(1, N):
        new_beam = []
        L = i + 1
        # 新たな行の自由変数として，中央 (1-indexed で (L+1)//2 番目) を使う
        pivot_index = (L + 1) // 2 - 1
        for row, curr_max_err in beam:
            # ターゲットとなる自由変数の値
            target_pivot = a[i][pivot_index]
            # ターゲット値の前後 delta_range 内の候補を試す
            for delta in range(-delta_range, delta_range + 1):
                pivot_val = (target_pivot + delta) % mod
                new_row = compute_row(row, pivot_index, pivot_val)
                # 新たな行の各セルでの誤差を計算
                row_errors = [error(new_row[j], a[i][j]) for j in range(L)]
                new_max_err = max(curr_max_err, max(row_errors))
                new_beam.append((new_row, new_max_err))
        # 評価の低いもの（誤差が小さいもの）をビーム幅内に残す
        new_beam.sort(key=lambda x: x[1])
        beam = new_beam[:beam_width]
    # 最終的に，ビーム中で最も誤差の低い候補の底辺を返す
    best_candidate = min(beam, key=lambda x: x[1])
    return best_candidate[0]

def main():
    import sys
    data = sys.stdin.read().strip().split()
    if not data:
        return
    N = int(data[0])
    a = []
    index = 1
    # 各段は 1, 2, …, N 個の整数
    for i in range(1, N + 1):
        row = []
        for _ in range(i):
            row.append(int(data[index]))
            index += 1
        a.append(row)
    bottom_row = beam_search(a, beam_width=10, delta_range=5)
    for num in bottom_row:
        print(num)

if __name__ == '__main__':
    main()
0