概要

\(N\) 本の柱すべてを倒壊させるために必要な最小の衝撃力 \(X\) を求める問題です。倒壊の判定は左から順に連鎖を考慮して行います。

考察

重要な気づき：\(X\) に対する単調性

\(X\) を大きくすればするほど、柱は倒壊しやすくなります。つまり：

• ある \(X\) ですべての柱が倒壊するなら、\(X' > X\) でもすべて倒壊する
• ある \(X\) で倒壊しない柱があるなら、\(X' < X\) でも倒壊しない柱がある

この単調性があるため、二分探索で最小の \(X\) を効率的に求められます。

判定関数の設計

\(X\) を固定したとき、すべての柱が倒壊するかを左から順にシミュレーションします。

• 柱 \(i\) が受けるダメージ \(= X +\)（左隣が倒壊していれば \(1\)、そうでなければ \(0\)）
• ダメージ \(\geq A_i\) なら柱 \(i\) は倒壊

すべての柱を倒壊させる必要があるので、途中で倒壊しない柱が1本でもあれば、その時点で失敗と判定できます（その柱自体が倒壊しないため）。

具体例

\(A = [3, 4, 2]\) の場合を考えます。

• \(X = 2\)：柱1のダメージ \(2 < 3\) → 倒壊せず → 失敗
• \(X = 3\)：柱1のダメージ \(3 \geq 3\) → 倒壊、柱2のダメージ \(3+1=4 \geq 4\) → 倒壊、柱3のダメージ \(3+1=4 \geq 2\) → 倒壊 → 成功

よって答えは \(X = 3\) です。

アルゴリズム

1. 二分探索の範囲を \(\text{lo} = 1\)、\(\text{hi} = \max(A)\) に設定する
2. \(\text{mid} = \lfloor (\text{lo} + \text{hi}) / 2 \rfloor\) として判定関数 check(mid) を呼ぶ
3. 判定関数 check(X)：
   • 左から順に各柱について、受けるダメージ（\(X\) ＋ 左隣の倒壊ボーナス）が耐久値以上か確認
   • 1本でも倒壊しなければ False、すべて倒壊すれば True
4. check(mid) が True なら \(\text{hi} = \text{mid}\)、False なら \(\text{lo} = \text{mid} + 1\)
5. \(\text{lo} = \text{hi}\) になったら、それが答え

補足：答えの直感的理解

実はすべての柱が連鎖的に倒壊するとき、必要な \(X\) は次のように表せます：

\[X = \max\!\Big(A_1,\;\max_{i=2}^{N}(A_i - 1)\Big)\]

• 最初の柱には連鎖ボーナスがないため \(X \geq A_1\) が必要
• 2番目以降の柱は左隣が倒壊していれば \(+1\) のボーナスがあるため \(X \geq A_i - 1\) で十分

二分探索はこの構造を明示的に導かなくても正しい答えに到達できるアプローチです。

計算量

• 時間計算量: \(O(N \log(\max(A)))\) — 二分探索が \(O(\log(\max(A)))\) 回、各回の判定が \(O(N)\)
• 空間計算量: \(O(N)\) — 配列 \(A\) の格納

実装のポイント

• 二分探索の範囲：\(X\) の下限は \(1\)（正の整数）、上限は \(\max(A)\)（連鎖ボーナスなしでも最大の柱を倒す力）で十分

• 判定関数での早期打ち切り：倒壊しない柱が見つかった時点で即座に False を返すことで、無駄な計算を省ける

• sys.stdin.buffer.read() を使った高速入力により、\(N\) が大きい場合でもTLEを回避

  ソースコード

import sys

def solve():
    data = sys.stdin.buffer.read().split()
    N = int(data[0])
    A = [int(data[i + 1]) for i in range(N)]

    def check(X):
        prev_collapsed = False
        for i in range(N):
            damage = X + (1 if prev_collapsed else 0)
            if damage >= A[i]:
                prev_collapsed = True
            else:
                return False
        return True

    lo, hi = 1, max(A)
    while lo < hi:
        mid = (lo + hi) // 2
        if check(mid):
            hi = mid
        else:
            lo = mid + 1

    print(lo)

solve()

---

この解説は claude4.6opus-thinking によって生成されました。