まず、数列 a[0], a[1], ..., a[N-1] と数列 b[0], b[1], ..., b[N-1] とを、それぞれ小さい順に並び替えておきましょう (ソートするといいます)。このように、数列をあらかじめ小さい順に並び替えておくことで問題が考えやすくなることは多々あります。なお、N 個の要素をソートするのは O(N log N) の計算量でできます (12 章参照)。
ここで、数列 b[0], b[1], ..., b[N-1] に対してこの順に、数列 a[0], a[1], ..., a[N-1] のどの要素とペアにしていけるかを考えていくことにしましょう。まず b[0] に対して、a[i] < b[0] となるような a[i] が存在しない場合は b[0] はペアを組むことができません。存在する場合は、たとえば a[0] と b[0] をペアにすればよいことがいえます (a[i] < b[0] を満たす a[i] であれば、どれをペアにしてもよいです)。
そのことを示してみましょう。b[0] を a[0] とペアにしないような最適解があったとします。このとき、この解を悪化させることなく (マッチングペアの個数を減らすことなく)、ペアを組み替えることで b[0] と a[0] が組む解へと変形できることを示します。まず、最適解において
a[i]とb[0]a[0]とb[j]
とがそれぞれペアを組んでいたとします (a[0] または b[0] のいずれかが誰ともペアを組んでいない場合は、ペアを組めるように繋ぎ直せばよいだけです)。このとき、
a[0] と b[0]a[i]とb[j]
というようにペアを組み直すことができます。なぜなら、a[0] <= a[i] < b[0]、a[i] < b[0] <= b[i] が成立するからです。
以上より、a[0] と b[0] とをペアにするような最適解が存在することが示せましたので、これらを除去して考えることにします。残りの値に対しても同様の手続きを繰り返していけばよいでしょう。
まとめると、次の方法で解くことができます。計算量は O(N log N) となります。
i = 0 とします
各 j = 0, 1, ..., N-1 に対して
a[i] < b[j]であるならば、a[i]とb[j]とをペアにしてi += 1とします- そうでないならば、スキップします (
b[j]は誰ともペアを組みません)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// (所要時間, 締め切り) のペア
using pll = pair<long long, long long>;
int main() {
// 入力
int N;
cin >> N;
vector<int> A(N), B(N);
for (int i = 0; i < N; ++i) cin >> A[i];
for (int i = 0; i < N; ++i) cin >> B[i];
// それぞれソートする
sort(A.begin(), A.end());
sort(B.begin(), B.end());
// B を順に見ていく
int i = 0;
for (int j = 0; j < N; ++j) {
if (A[i] < B[j]) ++i;
}
// i が答え
cout << i << endl;
}
問題 7.1 では一次元直線上の点同士のペアを組んでいく問題でしたが、今回は二次元平面上の点同士のペアを組んでいく問題です。難易度はだいぶ上がりますが、丁寧に考察することで解くことができます。具体的なアルゴリズムについては、次の記事に記しています。
AtCoder ARC 092 C - 2D Plane 2N Point
実社会でもたびたび登場しそうな問題ですね。多くの方が直感的に考えそうな通り、「締め切りが最も早いものから仕事をこなしていく」という方法が最適となります。具体的なアルゴリズムについては、次の記事に記しています。