はまやんはまやんはまやん

hamayanhamayan's blog

Exhausted? [AtCoder Regular Contest 076 F]

http://arc076.contest.atcoder.jp/tasks/arc076_d

公式放送

www.youtube.com
55:40頃から。これの副読本的に書きます。

解説

http://arc076.contest.atcoder.jp/submissions/1381916

O(2^N)解法 関数solveO2N
まず、ホールの定理の定理というのがある。
これは2部グラフ(A, B)とその間に辺があるとき、全てのAの部分グラフA'とそれに辺で繋がってるBの部分グラフB'に対して、
|A'|≧|B'|であるとき、Aのマッチング先が全てあることが言えるという定理である。

今回はこれに基いて、部分グラフAの全ての部分集合について、B'を計算する。
全ての部分集合の|A'| - |B'|の最大値が答えとなる。
これが、O(2^N)解法(のはずなのだが、これでやるとWAが出る)

 
O(M^2N)解法 関数solveOM2N
公式放送の1:08:00頃を見ると、「LとRを固定してやる」やり方の説明をしています。
LとRを固定すると
|A'|はL[i]がL以下、R[i]がR以上である人の個数
|B'|は椅子の個数で、(L + M + 1 - R)個
であるといえるので、|A'|を数えるのにO(N)かかり、全体でO(M^2N)

 
O(NlogM)解法 関数solveONlogM
これを高速化すると答えなのだが、Lを全探索することを考える。
Lは実際にはN人のLに対してだけやればいいので、高橋くんをL順でソートして順に処理していく。
|A'|-|B'| = human - (L + M + 1 - R) = human + R - (L + M + 1)
であり、Lが固定されているならば、後ろの引き算部分は一定となる。
なので、human+Rの最大値を効率よく取れれば答えが導ける。

まず、Rの部分を遅延セグメントツリーに予め入れておく。
そして、i番目の高橋くんを追加するときに、R[i]がR以上である人の個数を数えているので、[0,R[i])にRが来たときに自分がカウントされることになるため、[0,R[i])の区間に+1をする。
これで、区間全体を見たときの最大値がhuman+Rで取りうる最大値となる。

これで計算量がO(NlogM)となり解けた。

int N, M, L[201010], R[201010];
pair<int, int> LR[201010];
LazySegTree<int,1<<18> st;
int solveONlogM() { // O(NlogM)
    rep(i, 0, N) LR[i] = { L[i], R[i] };
    sort(LR, LR + N);

    rep(i, 1, M + 2) st.update(i, i + 1, i);

    int ans = max(0, N - M);
    rep(i, 0, N) {
        st.update(0, LR[i].second + 1, 1);

        // human - (LL + M + 1 - RR) = human + RR - (LL + M + 1)
        ans = max(ans, st.get(0, M + 2) - (LR[i].first + M + 1));
    }
    return ans;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, N) cin >> L[i] >> R[i];
    
    cout << solveONlogM() << endl;
}