トップ > AtCoder > ABC245E - Wrapping Chocolate

ABC245E - Wrapping Chocolate

AtCoder AtCoder-Beginner Contest 2変数 順序付集合 c++

頭がこんがらがる．．．

考え方

2次元座標で考えるのが大事．

チョコと箱を(縦, 横)でソートしておく．チョコの大きい順に見ていき，なるべくギリギリ入る箱を削除して（使って）いけば良い（使った箱しか候補から削除できない．「勘違いしたこと」を参照．）．

チョコはソート順に見ていくので配列でよいが，箱は

  • ソート順を保ったままの配列で，
  • 横の長さに対する二分探索を行い，
  • 途中で要素の追加 / 削除を行う
ため，順序付集合が必要になる．Pythonにはライブラリがなく，とても面倒なので，C++を使うのがよい．


原理的には，昇順で見ていくこともできそうだが，チョコを降順で見ていく場合は使える箱の「縦」の情報を捨てて良いのに対し，昇順で見ると「縦」の情報を捨てられない（降順で見る場合は，今見ているより「縦」が大きなチョコはないから，「縦」がチョコ以上の未使用の箱の中から「横」がギリギリのものを選べば良い．昇順で見る場合は，今見ているチョコより「縦」が大きな物があるから，「縦」も「横」もギリギリの箱を選ばなければならない）．

よって，チョコを降順に見ていく．

  1. 縦が一番大きいチョコを選ぶ．
  2. 今見ているチョコ以上の「縦の長さ」をもつ箱の「横の長さ」をmultisetにinsertする（※これ以降見るチョコの「縦」はmultisetに入っている「縦」以下なので，不要な情報．逆にあるとlower_boundが上手くいかなくなる．）．
  3. 「チョコの横」以上の横を持つ箱のなかで，最小のものをeraseする．これは，lower_boundで求められる．マッチング数をカウントするカウンタを+1する．
  4. 上記を全てのチョコに対して実行する．
  5. カウンタ=NならYes, そうでないならNoを出力する．

回答例

イテレータについて：AI - 4.04.イテレータ

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    vector<pair<int, int>> cho(N), box(M);
    for (int i = 0; i < N; i++) {
        cin >> cho.at(i).first;
    }
    for (int i = 0; i < N; i++) {
        cin >> cho.at(i).second;
    }
    for (int i = 0; i < M; i++) {
        cin >> box.at(i).first;
    }
    for (int i = 0; i < M; i++) {
        cin >> box.at(i).second;
    }
    sort(cho.rbegin(), cho.rend());
    sort(box.rbegin(), box.rend());
    multiset<int> s;
    auto it_box = box.begin();
    for (int i = 0; i < N; i++) {
        while (it_box < box.end() && (*it_box).first >= cho.at(i).first) {
            s.insert((*it_box).second);
            it_box++;
        }
        auto it_s = s.lower_bound(cho.at(i).second);
        if (it_s == s.end()) {
            cout << "No" << endl;
            return 0;
        }
        s.erase(it_s);
    }
    cout << "Yes" << endl;
    return 0;
}

【参考】AtCoder Beginner Contest 245 - YouTube (Submission #30488624 - AtCoder Beginner Contest 245)

勘違いしたこと

はじめ，チョコレートと箱をそれぞれソート（(縦, 横)でソート）しておけば，「$i$番目のチョコが$j$番目の箱に入らなければ，$i^{\prime} (> i)$番目のチョコは$j^{\prime} (\geq j)$番目の箱には入らない」と考えた．

もし，これが成り立つなら，以下のようにチョコと箱を小さい順に見て，入らない箱は捨てていけばよい．しかし，実際は上は成り立たず，チョコの順序と箱への入りやすさが逆転する例がある．例えば，

  • チョコ：[(1, 3), (2, 1)]
  • 箱：[(2, 2), (2, 3)]
だと，1番目の箱に1番目のチョコは入らないが，2番目のチョコは入る．

よって，チョコが入らないからと言って，箱を捨てることはできない．

【誤答】

N, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
D = list(map(int, input().split()))

cho = [(a, b) for a, b in zip(A, B)]
box = [(c, d) for c, d in zip(C, D)]
cho.sort(reverse = True)
box.sort(reverse = True)

cnt = 0
while (cho and box):
    a, b = cho.pop()
    while box:
        c, d = box.pop()
        if a <= c and b <= d:
            cnt += 1
            break

print('Yes' if cnt == N else 'No')