結果
問題 | No.5021 Addition Pyramid |
ユーザー |
![]() |
提出日時 | 2025-02-25 22:01:06 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 74 ms / 2,000 ms |
コード長 | 2,646 bytes |
コンパイル時間 | 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 |
ソースコード
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()