概要

\(N\) 本の柱をすべて倒壊させるために必要な、一斉に与える衝撃の最小値 \(X\) を求める問題です。左隣の柱が倒壊すると右隣の柱に追加ダメージが入るという連鎖規則を考慮する必要があります。

考察

すべての柱を倒壊させるという条件から、各柱が倒れるための条件を整理します。

1. 1番目の柱 (\(A_1\)) 左隣の柱が存在しないため、連鎖による追加ダメージはありません。したがって、自力で倒れるためには \(X \ge A_1\) である必要があります。
2. 2番目以降の柱 (\(A_i\), \(i \ge 2\)) 「すべての柱を倒す」ことが目標なので、2番目の柱を考えるときには、すでに1番目の柱が倒壊している前提で考えることができます。 1番目の柱が倒壊すると、2番目の柱には連鎖によるダメージ \(1\) が加わります。つまり、合計のダメージは \(X + 1\) となります。 これが耐久値 \(A_i\) 以上であればよいので、\(X + 1 \ge A_i\)、すなわち \(X \ge A_i - 1\) が条件となります。
3. 連鎖の累積について 問題文には「すぐ右隣の柱の耐久値がさらに 1 減少します」とあります。これは、左隣が倒れたことによるボーナスであり、さらにその左の柱たちが倒れていても、入る追加ダメージは常に \(1\) です。 したがって、どの \(i \ge 2\) についても、必要な衝撃は \(X \ge A_i - 1\) というシンプルな形になります。

以上のことから、すべての柱を倒すための最小の \(X\) は、以下の条件をすべて満たす最小の整数となります。 - \(X \ge A_1\) - \(X \ge A_2 - 1\) - \(X \ge A_3 - 1\) - \(\vdots\) - \(X \ge A_N - 1\)

これは、数式で表すと \(X = \max(A_1, A_2-1, A_3-1, \dots, A_N-1)\) となります。

アルゴリズム

1. 答えの候補となる変数 ans を \(A_1\) で初期化します。
2. \(i = 2\) から \(N\) まで順番に柱を見ていき、ans と \(A_i - 1\) の大きい方を新しい ans とします。
3. 最終的な ans を出力します。

計算量

• 時間計算量: \(O(N)\) 柱の数 \(N\) に対して 1 回のループで処理が終わるため、非常に高速です。
• 空間計算量: \(O(N)\) 入力をリストとして保持する場合に \(O(N)\) 必要です。

実装のポイント

• \(N\) が最大 \(5 \times 10^5\) と大きいため、Python の場合は sys.stdin.read().split() などを使って高速に入力を読み込むのが無難です。

• 最初の柱だけ条件が \(A_1\) そのままであり、2番目以降は \(A_i - 1\) になるという違いに注意してください。

  ソースコード

import sys

def solve():
    # Read all input data at once for speed
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: number of pillars
    n = int(input_data[0])
    # a: list of durabilities A_1, A_2, ..., A_N
    a = list(map(int, input_data[1:]))
    
    # The condition for all pillars to collapse:
    # 1. Pillar 1 must collapse from the initial shock X:
    #    X >= A_1
    # 2. For each pillar i (where i > 1), it collapses if its durability 
    #    minus (initial shock X + 1 if the previous pillar collapsed) is <= 0.
    #    Since we require all pillars to collapse, Pillar i-1 will have collapsed,
    #    giving Pillar i an additional 1 damage.
    #    So: X + 1 >= A_i  =>  X >= A_i - 1
    
    # Start with the requirement for the first pillar
    ans = a[0]
    
    # Check the requirement for all subsequent pillars
    for i in range(1, n):
        # The required X for pillar i+1 is A_{i+1} - 1
        if a[i] - 1 > ans:
            ans = a[i] - 1
            
    # Output the minimum force X
    print(ans)

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-thinking によって生成されました。