問題概要

$N$ 枚の絵画があって、それぞれ大きさは $S_i$ 、価値は $V_i$ で与えられる。

$M$ 個の額があって、それぞれ大きさが $C_i$ で与えられる。

絵画と額とをマッチングさせる。ここで、以下の条件を満たすような最大マッチングを求めよ。

絵画と額との各マッチングペアについて、額の大きさは絵画の大きさ以上である
マッチングペアを、絵画の価値と、額縁の大きさがともに広義単調増加になるように一列に並べることができる

制約

$1 \le N, M \le 10^{5}$

考えたこと

絵に価値による指標がないバージョン (便宜的に価値がすべて 0 とすればいい) については、有名な Greedy に解ける最大マッチング問題になっている。

今回も Greedy になりそうだという気持ちがある。「最適解に対して最適性を失わずに解を扱いやすい形に変形できることを示す」というよくある論法を駆使することを考えてみる。

まず、最適解において $k$ 組のマッチングができる場合、その解を使用する額縁については大きい方から順に $k$ 個であるように変形することは容易にできる。よって、大きい方から順に使うものと考えてよい。

また、絵を価値が高い順に並べたとき、

一番大きい額縁の相方となる絵は、最初に登場する額縁に入るサイズのもの

となるように解を悪化させずに変形することができる。同様に

二番目の額縁の相方となる絵は、一番目に選んだ絵の次以降に来る絵のうち最初に登場する額縁に入るサイズのもの
三番目の額縁の相方となる絵は、二番目に選んだ絵の次以降に来る絵のうち最初に登場する額縁に入るサイズのもの

となるように解を悪化させずに変形することができる。というわけで、以上の考察から、以下のような Greedy でよいことがわかる。

額縁を大きい順に並べる
絵は価値が大きい順に並べる (この順に絵を採用していくことになる)

としておいて、額縁が大きい順に、フィットする絵をマッチングさせて行けば OK。

コード

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using pint = pair<int,int>;

int main() {
    int N, M; cin >> N >> M;
    vector<pint> pic(N);
    for (int i = 0; i < N; ++i) cin >> pic[i].second >> pic[i].first;
    sort(pic.begin(), pic.end(), greater<pint>());
    vector<int> gaku(M);
    for (int i = 0; i < M; ++i) cin >> gaku[i];
    sort(gaku.begin(), gaku.end(), greater<int>());

    int i = 0, j = 0;
    for (; i < gaku.size(); ++i, ++j) {
        while (j < pic.size() && pic[j].second > gaku[i]) ++j;
        if (j == pic.size()) break;
    }
    cout << i << endl;
}

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

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

JOI 本選 2019 B - 展覧会 (AOJ 0659, 難易度 7)

問題概要

制約

考えたこと

コード