概要

区間を選んで高さを \(1\) ずつ下げる操作により、列を山型にするための最小操作回数を求めます。

重要なのは、山の頂点 \(k\) を固定すると、左側では「下がっている隣接差」、右側では「上がっている隣接差」だけがコストになることです。

考察

山型の頂点を \(k\) と決めたとします。

このとき必要な条件は次の通りです。

• 左側 \(1,2,\ldots,k\) は広義単調非減少
• 右側 \(k,k+1,\ldots,N\) は広義単調非増加

つまり、左側では

\[ H'_i \le H'_{i+1} \]

右側では

\[ H'_i \ge H'_{i+1} \]

を満たす必要があります。

左側で必要な操作回数

左側の隣接する \(i,i+1\) について、もし元の高さが

\[ H_i > H_{i+1} \]

なら、このままでは左側の単調非減少条件に反しています。

差を

\[ d = H_i - H_{i+1} \]

とすると、最終的に \(H'_i \le H'_{i+1}\) にするには、少なくとも区画 \(i\) を区画 \(i+1\) より \(d\) 回多く削る必要があります。

区間操作で「区画 \(i\) は削るが、区画 \(i+1\) は削らない」ためには、選ぶ区間の右端がちょうど \(i\) でなければなりません。

したがって、この隣接差を直すには少なくとも \(d\) 回の操作が必要です。

よって、左側に必要な操作回数は

\[ \sum_{i=1}^{k-1} \max(0, H_i - H_{i+1}) \]

になります。

右側で必要な操作回数

同様に、右側では単調非増加である必要があります。

もし

\[ H_i < H_{i+1} \]

なら、これは右側の条件に反しています。

差を

\[ d = H_{i+1} - H_i \]

とすると、区画 \(i+1\) を区画 \(i\) より \(d\) 回多く削る必要があります。

これは、選ぶ区間の左端がちょうど \(i+1\) である操作によって実現できます。

したがって、右側に必要な操作回数は

\[ \sum_{i=k}^{N-1} \max(0, H_{i+1} - H_i) \]

です。

頂点 \(k\) を固定したときの答え

以上より、頂点を \(k\) に固定したときの最小操作回数は

\[ \sum_{i=1}^{k-1} \max(0, H_i - H_{i+1}) + \sum_{i=k}^{N-1} \max(0, H_{i+1} - H_i) \]

です。

あとは、これをすべての \(k\) について最小化すればよいです。

素朴に各 \(k\) ごとに左右を走査すると \(O(N^2)\) になり、\(N \le 10^6\) では間に合いません。

そこで、左側のコストと右側のコストを累積的に更新します。

アルゴリズム

まず、頂点を \(k=1\) とした場合を考えます。

このとき左側は空なので、必要なのは右側を単調非増加にするコストだけです。

つまり、

\[ \sum_{i=1}^{N-1} \max(0, H_{i+1} - H_i) \]

を最初に計算します。

これを suffix_up とします。

また、左側のコストを prefix_down とし、初期値は \(0\) です。

次に、頂点を左から右へ動かしていきます。

頂点を \(k\) から \(k+1\) に動かすと、境界 \((k, k+1)\) が「右側」から「左側」に移ります。

そのため、

• もし \(H_k > H_{k+1}\) なら、左側コストに \(H_k - H_{k+1}\) を足す
• もし \(H_k < H_{k+1}\) なら、右側コストから \(H_{k+1} - H_k\) を引く

という更新を行います。

各位置で

\[ \text{prefix\_down} + \text{suffix\_up} \]

を計算し、その最小値が答えです。

例えば \(H = [3,1,4,2]\) の場合、

• \(k=1\): 右側の上りは \(1 \to 4\) なのでコスト \(3\)
• \(k=2\): 左側の下り \(3 \to 1\) が \(2\)、右側の上り \(1 \to 4\) が \(3\)、合計 \(5\)
• \(k=3\): 左側の下り \(3 \to 1\) が \(2\)、右側コスト \(0\)、合計 \(2\)
• \(k=4\): 左側の下り \(3 \to 1\) と \(4 \to 2\) で合計 \(4\)

よって答えは \(2\) です。

計算量

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

入力配列 \(H\) を保持するため \(O(N)\) です。追加で使う変数は定数個なので、追加メモリは \(O(1)\) です。

実装のポイント

• \(N=1\) の場合、すでに山型なので答えは \(0\) です。

• 答えは最大で \(10^{15}\) 程度になるため、C++ などでは long long が必要です。

• Python では整数のオーバーフローを気にする必要はありません。

• 実装では \(0\)-indexed で扱っているため、境界 \(i\) は H[i] と H[i+1] の間を表します。

  ソースコード

import sys

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

    if N == 1:
        print(0)
        return

    suffix_up = 0
    for i in range(N - 1):
        a = H[i]
        b = H[i + 1]
        if b > a:
            suffix_up += b - a

    prefix_down = 0
    ans = suffix_up

    for i in range(N - 1):
        a = H[i]
        b = H[i + 1]
        if a > b:
            prefix_down += a - b
        elif b > a:
            suffix_up -= b - a

        v = prefix_down + suffix_up
        if v < ans:
            ans = v

    print(ans)

if __name__ == "__main__":
    main()

---

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