けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 245 E - Wrapping Chocolate (水色, 500 点)

AtCoder AtCoder500点 ABC-E 水色diff Greedyなマッチング マッチング 二部マッチング 二部グラフ 区間 フロー グラフ問題 Greedy どちらも可なら厳しい方 二次元平面上のN点の問題 選択肢が広い方か狭い方から決めていく 交換しても悪化しないGreedy 難しいGreedy setの上手な使い方 データ構造 平面走査 lower_bound

これ！！！
ABC 091 C - 2D Plane 2N Point とほとんど同じ！！
ただ制約が大きいので、貪欲法を高速化する必要がありますね。

問題概要

N 個のチョコレートと、 M 個の箱があります。

  • i 番目のチョコレートはサイズ A_{i} \times B_{i} であり、
  • j 番目の箱はサイズ C_{j} \times D_{j} です

チョコレート i は、 A_{i} \le C_{j} かつ B_{i} \le D_{j} を満たすとき、箱 j に入れることができます。

すべてのチョコレートをいずれかの箱に入れた状態にすることができるかどうか判定してください。

ただし、1 つの箱には 1 つのチョコレートしか入れることができません。

制約

  • 1 \le N \le M \le 2 \times 10^{5}

貪欲法

貪欲法自体は、以前記事に書いたとおりです！！
最大マッチングを求めて、その値が N に一致するかどうかを判定すればよいでしょう。

drken1215.hatenablog.com

箱を縦 C_{j} が小さい順に見ていきます。そして、チョコレートの縦 A_{i} が C_{j} 以下であるようなチョコレートのうち、

「横の長さ B_{i} が D_{j} を超えない範囲で最大となるようなチョコレート i」

を選んで、そのチョコレート i を箱 j に入れていきます。そのチョコレート i は今後使えなくなります。

このアルゴリズムは、各箱に対して、該当するチョコレートを選ぼうとすると O(NM) の計算量となります。このままでは間に合いません。

データ構造を使う

ここでは std::multiset を利用して高速化しましょう。

箱 j について考えているとき、 A_{i} \le C_{j} を満たすチョコレートについての B_{i} をかきあつめた集合を multiset S で管理していたとします。

このとき、この集合の要素のうち、 D_{j} を超えない範囲で最大のものは S.upper_bound(D[j]) で取得できるイテレータをデクリメントすることで取得できます。

これによって全体の計算量は O(N + M \log N) となります。

コード

#include <bits/stdc++.h>
using namespace std;
using pll = pair<long long, long long>;

int main() {
    int N, M;
    cin >> N >> M;
    vector<pll> cho(N), box(M);
    for (int i = 0; i < N; ++i) cin >> cho[i].first;
    for (int i = 0; i < N; ++i) cin >> cho[i].second;
    for (int i = 0; i < M; ++i) cin >> box[i].first;
    for (int i = 0; i < M; ++i) cin >> box[i].second;

    // A, C が小さい順にソート
    sort(cho.begin(), cho.end());
    sort(box.begin(), box.end());

    // C が小さい順に見ていく
    multiset<int> S;
    int res = 0;
    int i = 0;
    for (int j = 0; j < M; ++j) {
        // A[i] <= C[j] となる範囲の i をすべて動かす
        while (i < N && cho[i].first <= box[j].first) {
            S.insert(cho[i].second);
            ++i;
        }

        // その範囲で最大値を取り出す
        if (S.empty()) continue;
        auto it = S.upper_bound(box[j].second);
        if (it == S.begin()) continue;
        --it;
        S.erase(it);
        ++res;
    }
    if (res == N) cout << "Yes" << endl;
    else cout << "No" << endl;
}