概要

この問題の本質は、連鎖が起きても各柱が追加で受けるダメージは高々 \(1\) だけ、という点です。
したがって、1本目は \(X\) だけで倒す必要があり、2本目以降は「左隣が倒れる」と仮定すれば \(X+1\) で倒せればよいので、答えは

\[ \max \left( A_1,\ \max_{2 \le i \le N}(A_i-1) \right) \]

となります。

考察

まず、各柱がどうやって倒れるかを整理します。

• すべての柱は最初に同時に \(X\) のダメージを受ける
• その後、左から順に見ていき、
  • もし左隣の柱が倒れていれば、その柱はさらに \(1\) ダメージを受ける

ここで大事なのは、

• 1本目 は左隣が存在しないので、受けるダメージは \(X\) だけ
• 2本目以降 は、左隣が倒れていれば受けるダメージは \(X+1\)

ということです。

重要な気づき

連鎖と聞くと「右に行くほどどんどん大きなダメージが伝わる」と思いがちですが、そうではありません。
各柱が追加で受けるのは 左隣からの \(1\) だけ です。

つまり、各柱の判定は次のようになります。

• 1本目が倒れる条件：\(A_1 \le X\)
• 2本目が倒れる条件：1本目が倒れていて、かつ \(A_2 \le X+1\)
• 3本目が倒れる条件：2本目が倒れていて、かつ \(A_3 \le X+1\)
• …

この形を見ると、最初の1本目さえ倒れれば、以降は全部「\(X+1\) で倒せるかどうか」だけ で決まります。

---

必要条件

すべて倒すには、当然

• 1本目について \(X \ge A_1\)
• 2本目以降について \(X+1 \ge A_i\)
  すなわち \(X \ge A_i-1\)

が必要です。

したがって、\(X\) は少なくとも

\[ \max \left( A_1,\ \max_{2 \le i \le N}(A_i-1) \right) \]

以上でなければなりません。

---

これで本当に十分か？

はい、十分です。
実際にこの値を \(X\) とすると、

• 1本目は \(A_1 \le X\) なので倒れる
• 1本目が倒れたので、2本目は \(X+1\) のダメージを受ける
• しかも \(A_2 \le X+1\) なので倒れる
• すると3本目も同様に倒れる
• …
• これを順に繰り返せば、すべての柱が倒れる

と分かります。

つまり、この値は「必要」でもあり「十分」でもあるので、そのまま最小値です。

---

具体例

例えば

\[ A = [5, 7, 6, 4] \]

のとき、

• 1本目のために \(X \ge 5\)
• 2本目以降のために
  • \(X \ge 7-1=6\)
  • \(X \ge 6-1=5\)
  • \(X \ge 4-1=3\)

なので答えは

\[ \max(5,6,5,3)=6 \]

です。

実際、\(X=6\) なら

• 1本目：\(6\) 受けて倒れる
• 2本目：\(6+1=7\) 受けて倒れる
• 3本目：\(7\) 受けて倒れる
• 4本目：\(7\) 受けて倒れる

となり、全部倒れます。

---

素朴な方法がなぜ不要か

素朴には、

• ある \(X\) を決めてシミュレーションする
• それをいろいろな \(X\) で試す

という方法が考えられます。

しかし \(A_i\) は最大 \(10^9\) なので、\(X\) を小さい方から順に試すのは到底間に合いません。

この問題は連鎖の仕組みを正しく読むと、実はシミュレーションすらほぼ不要で、
各柱に必要な条件を式にするだけで答えが一発で分かる のがポイントです。

アルゴリズム

以下を計算します。

1. 答えを最初は \(A_1\) にする
   （1本目は \(X\) だけで倒さなければならないため）
2. 2本目以降について、\(A_i-1\) を見て答えを更新する
3. 最後にその最大値を出力する

式で書くと、

\[ \text{ans} = \max \left( A_1,\ A_2-1,\ A_3-1,\ \dots,\ A_N-1 \right) \]

です。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\)

実装のポイント

• 1本目だけ条件が異なり、必要なのは \(A_1\) そのものです
• 2本目以降は「左隣が倒れるなら \(+1\) ダメージ」が入るので、必要条件は \(A_i-1\)
• Python では 0-indexed 配列なので、コードでは
  • A[0] が1本目
  • A[i] - 1 を i=1 から見ていけばよいです

この方針をそのまま実装したのが提出コードです。

ソースコード

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split()))
    
    ans = A[0]
    for i in range(1, N):
        ans = max(ans, A[i] - 1)
    
    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.4-high によって生成されました。