概要

この問題は、与えられた数列 \(H\) において、「両隣の要素よりも真に小さい」という条件を満たす要素（凹み）をすべてなくすために、要素の値を \(1\) 増やす操作を行う最小回数を求める問題です。

一見すると、ある場所の凹みを直した結果が他の場所に影響を及ぼしそうに見えますが、それぞれの凹みを解消する操作は互いに独立に決定できるため、貪欲法を用いて \(O(N)\) で解くことができます。

考察

1. 凹みを解消するための唯一の方法

ある区画 \(i\) が凹んでいる、すなわち \(H_{i-1} > H_i\) かつ \(H_i < H_{i+1}\) が成り立っているとします。 この凹みを解消するためには、以下のいずれかを満たすようにする必要があります。 - \(H_i \geq H_{i-1}\) にする - \(H_i \geq H_{i+1}\) にする

操作は「高さを増やす」ことしかできないため、両隣（\(H_{i-1}\) や \(H_{i+1}\)）を減らすことで凹みを解消することはできません。したがって、凹んでいる区画 \(H_i\) 自体の高さを増やすしかありません。

最小の操作回数で凹みを解消するためには、高さを \(\min(H_{i-1}, H_{i+1})\) まで引き上げれば十分です。このときに必要な操作回数は以下の通りになります。 $\( \min(H_{i-1}, H_{i+1}) - H_i \)$

2. 操作の独立性（他の区画への影響）

「ある区画 \(i\) の高さを上げたことで、隣の区画が新たに凹みになってしまうのではないか？」という疑問が生じます。

しかし、区画 \(i\) の高さを必要最小限である \(\min(H_{i-1}, H_{i+1})\) まで上げたとき、変更後の \(H_i\) は \(H_{i-1}\) または \(H_{i+1}\) の少なくとも一方と等しくなります。 凹みの条件は「両隣よりも真に（厳密に）小さい」ことであるため、隣り合う区画の高さが等しくなった場合、それらの区画が新たに凹みになることは絶対にありません。

また、ある区画の高さを上げたことで、他の区画の凹みが「連鎖的に勝手に解消される」こともありません。なぜなら、他の凹み \(j\) を解消するためには、やはり \(H_j\) 自体の高さを上げるしかないからです。

以上のことから、各区画の凹みは他の区画の状況に影響を与えず、独立に補修してよいことが分かります。したがって、元の配列の値を書き換えることすら不要で、各区画が凹んでいるかどうかを個別に判定して必要な操作回数を足し合わせるだけで正解となります。

アルゴリズム

1. \(N \leq 2\) の場合は、定義より凹みは存在しないため、答えは 0 です。
2. \(N \geq 3\) の場合、インデックス \(i\) を \(1\) から \(N-2\) までループさせます（0-indexedの場合）。
3. 各 \(i\) について、 \(H_i < H_{i-1}\) かつ \(H_i < H_{i+1}\) が成り立つ（＝凹んでいる）かを判定します。
4. 凹んでいる場合、必要な操作回数 \(\min(H_{i-1}, H_{i+1}) - H_i\) を答えの変数 ans に加算します。
5. ループ終了後、 ans を出力します。

計算量

• 時間計算量: \(O(N)\) 配列を左から右へ \(1\) 回走査するだけでよいため、線形時間 \(O(N)\) で処理が完了します。\(N = 10^6\) でも十分高速に実行可能です。
• 空間計算量: \(O(N)\) 入力された配列 \(H\) をメモリ上に保持するための空間です。

実装のポイント

• 配列の更新が不要: 考察の通り、ある凹みを直しても隣の判定に影響しないため、配列 H の要素を実際に書き換える必要はありません。これにより、実装が非常にシンプルになります。

• 高速な入出力: Pythonでは \(N = 10^6\) の入力が高速に行われないと実行時間制限（TLE）になる可能性があるため、sys.stdin.read().split() を用いて一括で入力を取得しています。

  ソースコード

import sys


def solve():
    # 入力を一括で読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    N = int(input_data[0])
    H = [int(x) for x in input_data[1:]]

    if N <= 2:
        print(0)
        return

    ans = 0
    # 凹んでいる区画を判定し、必要な操作回数を加算する
    for i in range(1, N - 1):
        h_curr = H[i]
        h_prev = H[i - 1]
        h_next = H[i + 1]
        if h_curr < h_prev and h_curr < h_next:
            ans += (h_prev if h_prev < h_next else h_next) - h_curr

    print(ans)


if __name__ == "__main__":
    solve()

---

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