概要

各柱は「自分への一撃 \(X\)」と「左隣が倒れていたら追加 \(1\)」で倒れるかが決まります。
この判定は左から一意に進むため、「ある \(X\) で全倒壊できるか」を高速に判定し、二分探索で最小の \(X\) を求めます。

考察

まず、ある固定した \(X\) について考えます。

左から順に見ていくと、柱 \(i\) の実際の耐久値は
- 基本で \(A_i - X\) - さらに左隣が倒れていれば \(-1\)

なので、判定条件は
$\(A_i - X - (\text{左隣が倒れていれば }1\text{、そうでなければ }0) \le 0\)$ です。

この問題の重要な点は、左から順に倒壊が確定することです。
柱 \(i\) が倒れるかどうかは、柱 \(i-1\) が倒れたかだけ見ればよく、右側の情報は不要です。

---

素朴に「\(X=1,2,3,\dots\) と順に試す」と、最悪で \(X\) は \(10^9\) 近く必要で間に合いません。
そこで次の単調性を使います：

• ある \(X\) で全て倒せるなら、\(X+1\) でも必ず倒せる（ダメージが増えるだけなので不利にならない）

つまり「全倒壊できるか」は \(X\) に対して単調（False…False, True…True）なので、二分探索が使えます。

アルゴリズム

1. ok(x) を定義する：
   「力 \(x\) で全柱を倒せるか」を \(O(N)\) で判定。
   • 左から順に見る
   • left_fallen（左隣が倒れたか）を持つ
   • 各柱で hp = A[i] - x - (1 if left_fallen else 0) を計算
   • hp > 0 ならその柱は生き残るので即 False
   • 倒れた場合は次の柱に連鎖するため left_fallen = True
2. 二分探索：
   • 探索範囲は \([1, \max A_i]\)
   • ok(mid) が真なら右端を縮める、偽なら左端を上げる
3. 収束した値が最小の \(X\)。

このコードでは、1本目が倒れなければ即 False になるため、left_fallen の更新は常に True で問題ありません（途中で生き残る時点で終了するため）。

計算量

• 時間計算量: \(O(N \log \max A)\)
• 空間計算量: \(O(1)\)（入力配列を除く）

実装のポイント

• 二分探索の上限を max(A) にしてよい理由：\(X=\max(A)\) なら少なくとも各柱にその値のダメージが入るため全倒壊可能。

• ok(x) は「生き残る柱が見つかったら即 False」にすると高速。

• Python では N=5\times10^5 なので sys.stdin.readline を使うと安全です。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N = int(input().strip())
    A = list(map(int, input().split()))

    def ok(x: int) -> bool:
        left_fallen = False
        for i in range(N):
            hp = A[i] - x - (1 if left_fallen else 0)
            if hp > 0:
                return False
            left_fallen = True
        return True

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

if __name__ == "__main__":
    main()

---

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