概要

区間を選んで高さを \(1\) 減らす操作を使って、列 \(H\) を山型にするための最小操作回数を求めます。

結論として、答えは

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

です。

考察

まず、「ある高さ列をすべて \(0\) にするには何回操作が必要か」を考えます。

高さ列を \(X_1, X_2, \ldots, X_N\) とします。
この列をすべて \(0\) にするための最小操作回数は

\[ X_1 + \sum_{i=2}^{N} \max(0, X_i - X_{i-1}) \]

です。

理由は、左から見ていくと分かりやすいです。

• \(1\) 番目の区画には \(X_1\) 個の「高さの層」があるので、少なくとも \(X_1\) 回の区間操作が必要です。
• \(i-1\) 番目から \(i\) 番目に進んだとき、もし \(X_i > X_{i-1}\) なら、新しく \(X_i - X_{i-1}\) 個の層が始まります。
• その分だけ新しい操作が必要になります。
• 逆に \(X_i \le X_{i-1}\) の場合、新しい層は始まらないので追加操作は不要です。

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

\[ 2 + \max(0,1-2) + \max(0,3-1) + \max(0,2-3) = 2 + 0 + 2 + 0 = 4 \]

回で全部 \(0\) にできます。

---

次に、最終的に残す列が山型である場合を考えます。

山型の列 \(A\) をすべて \(0\) にするための最小操作回数は、ちょうどその最大値になります。

なぜなら、山型では高さはピークまでは単調非減少、ピーク以降は単調非増加です。
そのため、左から見た「新しく始まる層」の数は、ピークの高さ、つまり \(\max A_i\) 個だけです。

---

ここで、元の列 \(H\) をいったん全部 \(0\) にするための最小回数を

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

とします。

もし \(m\) 回の操作で \(H\) を山型の列 \(A\) にできたとします。
その後、さらに \(A\) を全部 \(0\) にするには \(\max A_i\) 回必要です。

したがって、

\[ m + \max A_i \ge F(H) \]

が成り立ちます。

また、操作では高さを増やせないので、

\[ \max A_i \le \max H_i \]

です。

よって、

\[ m \ge F(H) - \max H_i \]

となります。

つまり、どんな方法でも少なくとも

\[ F(H) - \max H_i \]

回は必要です。

---

一方で、この回数で実際に山型にできます。

元の列を高さごとの「層」として見ます。
最大値を取る位置を \(p\) とします。

各高さレベルについて、位置 \(p\) を含む連続成分だけを残し、それ以外の層をすべて削ることを考えます。

すると残る高さ列は、

• \(p\) より左では、\(p\) に近づくほど高さが下がらない
• \(p\) より右では、\(p\) から離れるほど高さが上がらない

ので、必ず山型になります。

このとき残す層の数はちょうど \(\max H_i\) 個です。
元々すべて削るには \(F(H)\) 回必要なので、削る回数は

\[ F(H) - \max H_i \]

回になります。

したがって、下限と一致し、これが最小操作回数です。

アルゴリズム

求める値は

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

です。

したがって、左から一度走査しながら以下を計算します。

1. 最初の高さ \(H_1\) を記録する
2. 隣同士を比較し、\(H_i > H_{i-1}\) なら \(H_i - H_{i-1}\) を加算する
3. 全体の最大値 \(\max H_i\) を更新する
4. 最後に

\[ \text{答え} = H_1 + \text{増加分の合計} - \max H_i \]

を出力する

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

\[ H_1 = 2 \]

増加している部分は \(1 \to 3\) のみなので、

\[ \sum \max(0, H_i - H_{i-1}) = 2 \]

また、

\[ \max H_i = 3 \]

よって答えは

\[ 2 + 2 - 3 = 1 \]

です。

実際、\(1\) 番目だけを \(1\) 減らすと

\[ [2,1,3,2] \to [1,1,3,2] \]

となり、これは山型です。

計算量

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

実装のポイント

\(H_i\) は最大 \(10^9\)、\(N\) は最大 \(10^6\) なので、増加分の合計は \(32\) bit 整数に収まらない可能性があります。

そのため、答えや途中の合計は long long 型で扱う必要があります。

また、\(N=1\) の場合は元から必ず山型です。
この場合、

\[ H_1 - \max H_i = 0 \]

となるため、特別扱いしなくても答えは \(0\) になります。

ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    long long h, prev;
    cin >> h;

    long long first = h;
    long long maxH = h;
    long long totalRise = 0;
    prev = h;

    for (int i = 1; i < N; i++) {
        cin >> h;
        if (h > prev) totalRise += h - prev;
        maxH = max(maxH, h);
        prev = h;
    }

    cout << totalRise + first - maxH << '\n';
    return 0;
}

---

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