JOIさん、何故グラフ問を出してくれないのですか

JOI予選落ちが確定しました。 グラフが比較的得意だったので、グラフを絶対に通そうと思って練習してきたんですが、今年はなぜか出ませんでしたね。とてもかなしいです(出してくれよ...)
Dが簡単だったという声をよく聞くんですが、僕は解けませんでした...(つら🌾) くちもちくんに解説してもらったんですが、ちょっと詰まらせたのでメモ。考え方が典型っぽいしね。

日本列島、沈没させるか？出現させるか？

　小課題１

制約が N≦2000, Ai≦2000 なので、海面の高さを全探索しても間に合います。面倒なので愚直に沈没シミュレーションをします。
i == 0 と i == N の時の場合分けが面倒なので、Aを1-indexedにして、A[0] と A[N+1]に０を置いておきます。

#include<bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int (i)=0;(i)<(N);++(i))

int main(){
    int N;
    cin >> N;
    vector<int> A(N+1);
    rep(i,N) cin >>A[i+1];
    A[0] = 0;A.push_back(0);

    int ans = 0;
    for(int h=0;h<=2000;++h){
        int cnt = 0;
        for(int i=1;i<=N+1;++i){
            if(A[i] > h && A[i-1] <=h) cnt += 2;
            else if(A[i] <= h && A[i-1] > h) --cnt;
        } 
        ans = max(ans,cnt);
    }
    cout << ans << endl;
}

島の左端で+2して右端で-1することで島があれば1足すという操作を実現しています。

小課題2

よく考えると高さを全探索する必要はなくて、「海面がちょうどA[i]が沈む高さの時」だけ島の数が増減するのでこの時だけ見ればよいです。(僕はこれが出てきませんでした。たぴ。） より具体的には、A[i]について「海面の高さがA[i]未満」の時の島の数が分かればよいです。 （A[i]以下にすると、全部mとかのコーナーケースに引っ掛かるので未満にしました。海面が０の時を調べればいいんですがめんどうなので)
N ^ 2が間に合うので

#include<bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int (i)=0;(i)<(N);++(i))

int main(){
    int N;
    cin >> N;
    vector<int> A(N+1);
    set<int> st;
    for(int i=1;i<=N;++i)cin >> A[i],st.insert(A[i]);
    A[0] = 0; A.emplace_back(0);

    int ans = 0;
    for(int h : st){
        int cnt = 0;
        for(int i=1;i<=N+1;++i){
            if(A[i] >= h && A[i-1] < h) cnt += 2;
            else if(A[i] < h && A[i-1] >= h) --cnt;
        } 
        ans = max(ans,cnt);
    }

    cout << ans << endl;
}

このようにA[i]をsetに突っ込んであげて、小課題１と同じように島の数を調べていきます。

小課題３

制約が ・1≦N≦100000(=105) ・0≦Ai≦1000000000(=109) (1≦i≦N) なので、N ^ 2が通りません。今までの方法ではできないので、別の方法を考えます。 よく考えると、島の数はある高さまで増加して、そこから減少していきます。 なので高さを昇順か降順に見ていき、今の島の数を持っておいて島の数を増減させればNでいけそうです。

個人的には沈めたいんですが、全部０の時の場合分けが面倒なので†出現†させます。

#include<bits/stdc++.h>
using namespace std;
using P = pair<int,int>;
#define rep(i,N) for(int (i)=0;(i)<(N);++(i))

int main(){
    int N;
    cin >> N;
    vector<int> A(N+1);  A[0] = -1; 

    for(int i=1;i<=N;++i) cin >> A[i];
    auto res = unique(A.begin(),A.end());
    A.erase(res,A.end());

    priority_queue<P,vector<P>> que;
    for(int i=1;i<A.size();++i) que.push({A[i],i});
    A.emplace_back(0);
    que.push({0,1});

    int island = 0,ans = 0; 
    int now_h = 1e9+7;
    int p[3] = {-1,0,1};

    while(!que.empty()){
        P h = que.top(); que.pop();
        int cnt = 0;
        if(now_h != h.first) ans = max(ans,island);
        now_h = h.first;
        if(A[h.second-1] < h.first) ++cnt;
        if(A[h.second+1] < h.first) ++cnt;
        island += p[cnt];
    }
    cout << ans << endl;
}

高さを降順にとりだすのは、priority_queueにぶん投げます。 同じ高さの区画をすべて取り出してから更新するようにするとこわれません(n敗)

次に島の数の増減を考えます。図を描くと

A[i]が両隣より高いとき島が増える
A[i]が両隣のどちらか片方だけより高いとき、島の数は変わらない
A[i]が両隣よりも低いとき島が減る

ことがわかります。 ifを書くのは面倒なので、隣より高ければcntを+1してcntに応じて増減させています。 ここで、僕はもっと早く気が付くべきだったんですが、下の図のようなときにこわれます。

これは、ひとつずつ見ていったときに、島が増える条件を満たすものがないからです。 同じ高さが連続しているときにこわれることがわかったので、連続しているものを圧縮したい気持ちになります。 そこで登場するのがuniqueちゃんです。

この関数は、隣り合った重複要素を除いた要素を、範囲の先頭に集める。この関数によってコンテナから直接要素が削除され、コンテナの要素数が減るようなことはない。コンテナから実際に要素を削除する場合は、この関数の戻り値として、先頭に集められた重複なし範囲の末尾の次を指すイテレータが返るため、そのイテレータを介してコンテナのerase()メンバ関数などを呼び出し、削除を行うこと。

これ、ただ単に重複要素を後ろに持ってくるだけだと思っていたんですが、隣合う重複要素限定なんですね... これを使うことで連続している部分を圧縮できます。 これで、こわれることがなくなったのでこの問題が解けました。

必要ない部分を見ない、前回の値を使って更新していくというのは典型感があるのでこれを機にしっかり身に着けていきたいですね