日本沈没 (Japan Sinks) [第18回日本情報オリンピック 予選 D]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/JOI/Prelim/0655?year=2019

解説

https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0655/judge/3760197/C++14

海面の高さが上昇すると、島が分割または消滅していって、まとまりの個数を数えていく問題である。
一般に分割操作というのは、すこし面倒である。
なので、逆を考えてみる。
典型テクなのだが「時間を逆に見ることで分割操作ではなく、併合操作によって問題が解決できる」を使う。

今回でいうと、海面の高さを最初∞にしておいて、0まで下げていこう。
最初はまとまりの個数totは0である。 すると、陸地が出現してくると思うのだが、左右どちらにも陸地がない場合は、まとまりの個数は+1される。
片側だけ陸地が既にあった場合は、まとまりの個数は変わらない。
両側に陸地があった場合は、まとまりの個数は-1される。
これを順番に行っていって、totの最大値が答えになる。

注意だが、最大値を取るときは、同じ島の高さのものは全て処理してから行うこと。
もう一つ注意だが、高さが0の山は陸地になることは無いので、A[i]==0は結合しないようにする。

int N, A[101010];
int up[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];

    map<int, vector<int>> buf;
    rep(i, 0, N) if(0 < A[i]) buf[A[i]].push_back(i);

    int ans = 0;
    int tot = 0;
    for (auto ite = buf.rbegin(); ite != buf.rend(); ite++)
    {
        auto v = ite->second;

        fore(i, v) {
            up[i] = true;

            int yoko = 0;
            if (0 < i and up[i - 1]) yoko++;
            if (i + 1 < N and up[i + 1]) yoko++;

            if (yoko == 0) tot++;
            else if (yoko == 2) tot--;
        }

        chmax(ans, tot);
    }

    cout << ans << endl;
}