AtCoder Regular Contest 046 C - 合コン大作戦

問題

　人の男性と人の女性が合コンをした。男性は年収が円であり、年収が円以上の女性とカップルになりたいと考えている。女性もまた年収と相手の年収の希望を持っている。これらが同時に満たされるとカップルが成立するとき、最大のカップル数を求めよ。

解法

　男性と女性を混ぜて、男性は年収、女性は希望する相手の年収でソートし、小さい方から見ていく。今考えている人物が女性であれば年収をmultisetに突っ込んでいき、男性であればmultisetの中で希望年収以上であるものを一つ取り出す。この取り出す操作が可能であった回数が答えとなる。

反省

　1時間25分(3WA)でAC。40分を過ぎたあたりで男女を混ぜてそれぞれの値でソートすればいいということに気づいて実装して58分が過ぎたあたりで提出したがWA。自信があったのに取らなくて落胆してしまい、解説スライドを見た。解法は考えていたものと同じようなことが書かれていて、何が間違っているのかわからなくて結構悩んだ。

　一つにはまずmultisetではなくただのsetを使っていたというミスがあるのはわかったけれど、それを修正しても通らず。mapでやっている人が多かったのでそうしてみたがそれでも通らなかった。違う部分にミスがあると判断してコードを見直したところ、ソートするときに余計なものを考慮していたせいで順番がめちゃくちゃになってしまっていた。それを修正してAC。惜しいところまで行っていたので自力で通したかった……。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N, M;
    cin >> N >> M;

    enum {
        //男が後になるようにソートされて欲しいのでこの順番
        FEMALE, MALE
    };
    struct Human {
        ll income, hope, sex;
    };
    vector<Human> humans(N + M);
    for (ll i = 0; i < N; i++) {
        cin >> humans[i].income >> humans[i].hope;
        humans[i].sex = MALE;
    }
    for (ll i = 0; i < M; i++) {
        cin >> humans[N + i].income >> humans[N + i].hope;
        humans[N + i].sex = FEMALE;
    }

    sort(humans.begin(), humans.end(), [&](Human& lhs, Human& rhs) {
        ll l1 = (lhs.sex == MALE ? lhs.income : lhs.hope);
        ll r1 = (rhs.sex == MALE ? rhs.income : rhs.hope);

        return (l1 == r1 ? lhs.sex < rhs.sex : l1 < r1);
    });
    
    ll ans = 0;
    multiset<ll> women_income;
    for (auto h : humans) {
        if (h.sex == MALE) {
            auto pair = women_income.lower_bound(h.hope);
            if (pair != women_income.end()) {
                ans++;
                women_income.erase(pair);
            }
        } else {
            women_income.insert(h.income);
        }
    }

    cout << ans << endl;
}