概要

一直線に並ぶ \(N\) 個の区画の高さが与えられます。各区画の高さを \(1\) ずつ増やす操作を繰り返し、「左隣と右隣のどちらよりも真に低い区画（凹み）」をすべてなくすための最小操作回数を求める問題です。

考察

まず、凹んでいる区画 \(i\) をなくすには、区画 \(i\) の高さ \(H_i\) を上げるしかありません。凹みの条件は「\(H_{i-1} > H_i\) かつ \(H_i < H_{i+1}\)」なので、これを満たさなくするには \(H_i\) を \(H_{i-1}\) 以上か \(H_{i+1}\) 以上にすればよいです。

操作回数を最小にするためには、\(H_i\) を \(H_{i-1}\) と \(H_{i+1}\) のうち小さい方（\(\min(H_{i-1}, H_{i+1})\)）まで上げるのが最適です。これにより、少なくともどちらか一方の隣接区画と高さが等しくなるか高くなり、凹みの条件（真に小さい）を満たさなくなります。

ここで問題となるのが、「\(H_i\) を上げた結果、新たに別の区画が凹んでしまうのではないか？」ということです。特に右隣の区画 \(i+1\) が凹んでしまう条件は「\(H_i > H_{i+1}\) かつ \(H_{i+1} < H_{i+2}\)」です。 もし \(H_i\) を \(\min(H_{i-1}, H_{i+1})\) まで上げた場合、\(H_i = \min(H_{i-1}, H_{i+1}) \leq H_{i+1}\) となります。したがって、\(H_i > H_{i+1}\) になることは絶対にありません。

これにより、「左から右へ順に区画を見ていき、凹んでいたら左隣と右隣の低い方まで高さを上げる」という貪欲法で、右隣に新たな凹みを作ることなくすべての凹みを解消できることがわかります。後戻りする必要がないため、1回の走査で完了します。

アルゴリズム

1. \(N \leq 2\) の場合、凹みとなる区画は存在しないため 0 を出力して終了します。
2. 左から右へ \(i = 1\) から \(N-2\) までループを回します（0-indexedの場合）。
3. もし \(H_{i-1} > H_i\) かつ \(H_i < H_{i+1}\) であれば、区画 \(i\) は凹んでいます。
4. 目標の高さ target を \(\min(H_{i-1}, H_{i+1})\) として求めます。
5. ans に target - H_i を加算し、現在の高さ \(H_i\) を target に更新します。
6. ループ終了後、ans を出力します。

計算量

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

実装のポイント

• 左から右へ処理する際に、配列 \(H\) の要素を実際に更新していくことが重要です。これにより、次の区画を判定する際に、直前の区画が補修された後の正しい高さを使用できます。

• Pythonの組み込み関数 min を使うか、三項演算子を用いて H[i - 1] if H[i - 1] < H[i + 1] else H[i + 1] と書くことで、わずかな高速化が期待できます。

  ソースコード

import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    if N <= 2:
        print(0)
        return
    H = list(map(int, input().split()))
    ans = 0
    for i in range(1, N - 1):
        if H[i - 1] > H[i] and H[i] < H[i + 1]:
            target = H[i - 1] if H[i - 1] < H[i + 1] else H[i + 1]
            ans += target - H[i]
            H[i] = target
    print(ans)

if __name__ == '__main__':
    solve()

この解説は or-glm5.2-high によって生成されました。