概要

道路の各区画の高さが与えられ、両隣の高さよりも低い区画（凹み）をなくすために必要な最小操作回数（高さを1増やす操作）を求める問題です。

考察

まず、区画 \(i\) が凹んでいるという条件は「\(H_{i-1} > H_i\) かつ \(H_i < H_{i+1}\)」です。これを解消するには、高さを減らすことはできないため、\(H_i\) の高さを増やすしかありません。 最小の増加量で凹みを解消するには、\(H_i\) を左隣と右隣のどちらか低い方、すなわち \(\min(H_{i-1}, H_{i+1})\) まで増やせばよいと考えます。このとき、必要な操作回数は \(\min(H_{i-1}, H_{i+1}) - H_i\) 回となります。

しかし、問題文には「ある区画の路面の高さを上げた結果、別の区画が新たに凹みの条件を満たすようになる場合がある」という注意書きがあります。これについて確認します。 区画 \(i\) の高さを \(\min(H_{i-1}, H_{i+1})\) まで上げたとします。このとき、\(H_i \le H_{i+1}\) かつ \(H_i \le H_{i-1}\) が成り立ちます（高々等しくなるまでしか上げないため）。 新たな凹みができるためには、両隣の区画 \(i-1\) や \(i+1\) が凹む条件、すなわち「\(H_{i-2} > H_{i-1} < H_i\)」または「\(H_i > H_{i+1} < H_{i+2}\)」が成立する必要があります。 しかし、\(H_i\) を上げても \(H_{i-1} < H_i\) になることはなく（高々等しい）、同様に \(H_i > H_{i+1}\) になることもありません。したがって、高さを \(\min(H_{i-1}, H_{i+1})\) まで上げる限り、両隣の区画が新たに凹むことはありません。むしろ、両隣がすでに凹んでいた場合は、\(H_i\) が上がることでその凹みが解消される方向に働きます。

結論として、各区画の凹みは互いに独立に解消していくことができ、各凹みに対して \(\min(H_{i-1}, H_{i+1}) - H_i\) を足し合わせるだけで最小操作回数が求まります。

アルゴリズム

1. 高さの配列 \(H\) を入力として受け取る。
2. 答えを格納する変数（オーバーフローに注意し long long などの広い型を使う）を用意する。
3. \(i = 1\) から \(N - 2\) まで（0-indexedの場合）ループを回す。
4. もし \(H[i-1] > H[i]\) かつ \(H[i] < H[i+1]\) であれば、凹んでいるので、答えに \(\min(H[i-1], H[i+1]) - H[i]\) を加算する。
5. 最後に答えを出力する。

計算量

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

実装のポイント

• \(N \leq 2\) の場合は両端以外の区画が存在しないため、ループの範囲 \(1 \leq i \leq N-2\) が空になり、自動的に正しく 0 が出力されます。

• \(H_i\) や操作回数の上限が大きいため、答えの合計値は32ビット整数（int 型）の範囲を超える可能性があります。そのため、C++では long long 型などを使用する必要があります。

  ソースコード

#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);
    for (int i = 0; i < N; ++i) {
        cin >> H[i];
    }
    
    long long ans = 0;
    for (int i = 1; i < N - 1; ++i) {
        if (H[i - 1] > H[i] && H[i] < H[i + 1]) {
            ans += min(H[i - 1], H[i + 1]) - H[i];
        }
    }
    
    cout << ans << "\n";
    return 0;
}

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