概要

この問題は、与えられた数列 \(H\) に対し、「区間を \(1\) 減らす」という操作を繰り返して、特定の要素 \(H'_k\) を頂点とする山型の数列 \(H'\) を作るための最小操作回数を求める問題です。

制約が \(N \le 10^6\) と大きいため、山頂となる位置 \(k\)（ \(1 \le k \le N\) ）をすべて試し、各 \(k\) について最小操作回数を \(O(1)\) で計算することで、全体として \(O(N)\) で解くアプローチをとります。

---

考察

1. 山頂 \(k\) の固定

最終的な数列 \(H'\) が山型であるとは、ある頂点 \(k\) が存在して、左側（ \(1 \le i \le k\) ）が広義単調非減少、右側（ \(k \le i \le N\) ）が広義単調非増加になることです。 端点での処理を統一するため、数列の両端に \(H_0 = 0, H_{N+1} = 0\) を追加して考えます。

頂点 \(k\) を固定したとき、満たすべき条件は以下の通りです： - 左側： \(0 = H'_0 \le H'_1 \le H'_2 \le \cdots \le H'_k\) - 右側： \(H'_k \ge H'_{k+1} \ge \cdots \ge H'_N \ge H'_{N+1} = 0\)

2. 左側を単調非減少にするための操作回数

左側 \(1 \dots k\) を単調非減少にするためには、隣接する要素で減少している箇所（ \(H_{i-1} > H_i\) ）を解消する必要があります。区間を減らす操作を用いてこれを解消するには、減少している部分の左側を削る必要があります。

頂点 \(k\) の最終的な高さを \(H'_k\) と決めたとき、左側を単調非減少にするための最小操作回数 \(C_L(H'_k)\) は次のように表せます： $\(C_L(H'_k) = L_k - H'_k\)\( ここで \)L_k\( は、元の数列の \)0 \dots k\( における「上昇量（ \)Hi - H{i-1} > 0$ である差分）」の総和です。

具体例での確認

\(H = [0, 3, 1, 4]\) で \(k=3\) （ \(H_3 = 4\) ）とします。 - 上昇量の和 \(L_3 = (3 - 0) + (4 - 1) = 6\) - 減少量の和 \(sumB[3] = (3 - 1) = 2\)

左側を単調非減少にするには、減少している \(3 \to 1\) の段差（減少量 2）を解消するため、左側の \(3\) を \(1\) まで削る必要があります。この操作により数列は \([1, 1, 4]\) となり、操作回数は \(2\) 回です。このとき、頂点の高さは \(4\) のままです。 さらに頂点の高さを \(H'_3 = 2\) まで下げたい場合、追加で \(2\) 回操作を行い \([1, 1, 2]\) にします。合計操作回数は \(2 + 2 = 4\) 回となります。 これは、公式 \(C_L(H'_3) = L_3 - H'_3 = 6 - 2 = 4\) と一致します。

3. 右側を単調非増加にするための操作回数

同様に、右側 \(k \dots N+1\) を単調非増加（右から左に見れば単調非減少）にし、頂点 \(k\) の高さを \(H'_k\) にするための最小操作回数 \(C_R(H'_k)\) は、右側からの上昇量の累積を用いて次のように表せます： $\(C_R(H'_k) = D_k - H'_k\)\( ここで \)Dk\( は、元の数列の \)k \dots N+1\( における「減少量（ \)H{i-1} - H_i > 0$ である差分）」の総和です。

4. 左右の操作の統合（共通化）

左側を単調非減少にする操作と、右側を単調非増加にする操作は、頂点 \(k\) を跨ぐ区間 \([l, r]\) （ \(l \le k \le r\) ）を同時にデクリメントすることで共通化できます。 共通化できる回数は、頂点 \(k\) を元の高さ \(H_k\) から \(H'_k\) まで下げる量（ \(H_k - H'_k\) ）が上限となります。 したがって、全体の最小操作回数 \(\text{Cost}(H'_k)\) は以下のようになります： $\(\text{Cost}(H'_k) = C_L(H'_k) + C_R(H'_k) - \min(H_k - H'_k, C_L(H'_k), C_R(H'_k))\)$

ここに \(C_L(H'_k) = L_k - H'_k\) と \(C_R(H'_k) = D_k - H'_k\) を代入して整理すると、\(\min\) の中身は常に \(H_k - H'_k\) となり、式は以下のように非常にシンプルになります： $\(\text{Cost}(H'_k) = L_k + R_k - H'_k\)\( （ただし、 \)R_k = D_k - H_k\( であり、これは \)k \dots N+1$ における上昇量の総和に相当します）

5. \(H'_k\) の決定

コストを最小化するためには、引き算している \(H'_k\) をできるだけ大きくすればよいです。 ただし、操作回数は \(0\) 以上でなければならず、また元の高さより高くすることはできないため、以下の制約を満たす必要があります： - \(H'_k \le H_k\) - \(H'_k \le L_k\) （ \(C_L(H'_k) \ge 0\) より） - \(H'_k \le D_k\) （ \(C_R(H'_k) \ge 0\) より）

したがって、最適な \(H'_k\) の値は \(min\_val = \min(\{H_k, L_k, D_k\})\) となり、このときの最小コストは \(L_k + R_k - min\_val\) と求まります。

---

アルゴリズム

1. 数列の両端に \(H_0 = 0, H_{N+1} = 0\) を追加します。
2. 各隣接差の上昇量 \(A_i = \max(0, H_i - H_{i-1})\) と減少量 \(B_i = \max(0, H_{i-1} - H_i)\) を計算します。
3. \(A_i, B_i\) の累積和 \(sumA, sumB\) を事前に計算しておきます。これにより、任意の \(k\) に対して以下の値を \(O(1)\) で取得可能になります：
   • \(L_k = sumA[k]\)
   • \(R_k = sumA[N+1] - sumA[k]\)
   • \(D_k = sumB[N+1] - sumB[k]\)
4. \(k = 1\) から \(N\) までループを回し、各 \(k\) に対するコスト \(L_k + R_k - \min(\{H_k, L_k, D_k\})\) の最小値を求めます。

---

計算量

• 時間計算量: \(O(N)\) 累積和の構築に \(O(N)\)、各 \(k\) の探索は \(O(1)\) で行えるため、全体で線形時間 \(O(N)\) で動作します。
• 空間計算量: \(O(N)\) 元の配列および累積和配列を保持するために \(O(N)\) のメモリを使用します。

---

実装のポイント

• 高さ \(H_i\) は最大で \(10^9\) であり、累積和の最大値は \(10^{15}\) 程度に達するため、オーバーフローを防ぐために C++ では long long 型を使用する必要があります。

• \(N = 10^6\) と入力が非常に大きいため、std::cin.tie(NULL) などの高速入出力の記述を入れておくことが推奨されます。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // 高速な入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    if (!(cin >> N)) return 0;

    vector<long long> H(N + 2, 0);
    for (int i = 1; i <= N; ++i) {
        cin >> H[i];
    }
    H[0] = 0;
    H[N + 1] = 0;

    vector<long long> A(N + 2, 0);
    vector<long long> B(N + 2, 0);
    for (int i = 1; i <= N + 1; ++i) {
        A[i] = max(0LL, H[i] - H[i - 1]);
        B[i] = max(0LL, H[i - 1] - H[i]);
    }

    vector<long long> sumA(N + 2, 0);
    vector<long long> sumB(N + 2, 0);
    for (int i = 1; i <= N + 1; ++i) {
        sumA[i] = sumA[i - 1] + A[i];
        sumB[i] = sumB[i - 1] + B[i];
    }

    long long min_cost = -1;
    for (int k = 1; k <= N; ++k) {
        long long L_k = sumA[k];
        long long R_k = sumA[N + 1] - sumA[k];
        long long D_k = sumB[N + 1] - sumB[k];
        long long min_val = min({H[k], L_k, D_k});
        long long cost = R_k + L_k - min_val;
        if (min_cost == -1 || cost < min_cost) {
            min_cost = cost;
        }
    }

    cout << min_cost << "\n";

    return 0;
}

---

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