概要

各区画の高さを増やす操作だけで、左右より真に低い「凹み」をすべてなくす問題です。

重要なのは、凹んでいる区画ごとに「少なくともどこまで高さを上げる必要があるか」を考えると、各凹みを独立に処理できることです。

考察

区画 \(i\) が凹んでいるとは、

\(H_{i-1} > H_i\) かつ \(H_i < H_{i+1}\)

が成り立つことです。

このとき、区画 \(i\) の凹みをなくすには、\(H_i\) を少なくとも左右どちらかの高さ以上にする必要があります。

つまり、左右の高さをそれぞれ

• 左：\(H_{i-1}\)
• 右：\(H_{i+1}\)

とすると、\(H_i\) を

\(\min(H_{i-1}, H_{i+1})\)

まで上げれば十分です。

必要な操作回数は、

\(\min(H_{i-1}, H_{i+1}) - H_i\)

です。

例えば、高さが次のような場合を考えます。

\([5, 2, 4]\)

中央の \(2\) は左右の \(5, 4\) より低いので凹みです。

この凹みをなくすには、中央を少なくとも \(4\) まで上げればよいです。

\([5, 4, 4]\)

となり、中央は右隣と同じ高さなので、もはや「左右より真に低い」状態ではありません。

必要な操作回数は \(4 - 2 = 2\) 回です。

---

素朴に「凹みを見つけて 1 ずつ高さを上げる」というシミュレーションをすると、高さが最大 \(10^9\) なので操作回数が非常に多くなり、TLE してしまいます。

また、一見すると、ある区画を上げることで別の区画が新たに凹む可能性がありそうに見えます。

しかし、この問題では次の性質があります。

• 凹んでいる区画の隣の区画は、同時に凹みにはならない
• 凹んでいる区画を \(\min(H_{i-1}, H_{i+1})\) まで上げても、隣の区画が新たに凹みになることはない

なぜなら、区画 \(i\) が凹みなら、左右の区画は \(H_i\) より高いです。

\(H_i\) を \(\min(H_{i-1}, H_{i+1})\) まで上げても、上げた後の高さは左右のどちらかと等しくなります。

そのため、区画 \(i\) 自身は凹みではなくなります。

さらに、隣の区画から見ると、上げられた区画の高さは隣の区画以下になります。したがって、隣の区画が「左右両方より低い」状態になることもありません。

よって、最初に凹んでいる区画だけを見て、それぞれに必要な操作回数を足し合わせればよいです。

アルゴリズム

すべての区画 \(i\) について、\(2 \leq i \leq N-1\) の範囲を調べます。

区画 \(i\) が凹みである、つまり

\(H_{i-1} > H_i\) かつ \(H_i < H_{i+1}\)

を満たすなら、この区画を

\(\min(H_{i-1}, H_{i+1})\)

まで上げる必要があります。

そのため、答えに

\(\min(H_{i-1}, H_{i+1}) - H_i\)

を加えます。

これをすべての内部区画について行えば、最小操作回数が求まります。

例として、

\([5, 1, 4, 1, 5]\)

を考えます。

• 区画 \(2\) は \(5 > 1 < 4\) なので凹み
  • \(1\) から \(\min(5,4)=4\) まで上げる
  • 操作回数は \(3\)
• 区画 \(4\) は \(4 > 1 < 5\) なので凹み
  • \(1\) から \(\min(4,5)=4\) まで上げる
  • 操作回数は \(3\)

合計で \(3+3=6\) 回です。

最終的に例えば

\([5, 4, 4, 4, 5]\)

となり、凹みはありません。

計算量

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

実装のポイント

\(N \leq 2\) の場合、内部の区画が存在しないため、凹みも存在しません。

したがって、答えは常に \(0\) です。

また、\(N\) は最大で \(10^6\) と大きいので、Python では sys.stdin.buffer.readline を使って高速に入力を読み取っています。

ソースコード

import sys

def main():
    input = sys.stdin.buffer.readline
    n = int(input())
    h = list(map(int, input().split()))

    if n <= 2:
        print(0)
        return

    ans = 0
    for i in range(1, n - 1):
        hi = h[i]
        if h[i - 1] > hi and hi < h[i + 1]:
            left = h[i - 1]
            right = h[i + 1]
            ans += (left if left < right else right) - hi

    print(ans)

if __name__ == "__main__":
    main()

---

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