AtCoder Beginner Contest 091_C_2D Plane 2N Points
Greedyの問題.どうマッチングさせると仲良しさんが作られるか.
問題の説明
赤い点の外側にある青い点を結ぶことで作る事の出来るペアの個数の最大値を求めよ.
ただしで
かつ
のとき,
は
の外側にあるという.
条件
- 赤い点と青い点の
座標,
座標は全て相異なる.
考えた事
最初考えた事は,赤い点からどのように青い点を選べばペアを多く作れるかであった.そういった中で,なるべく座標の差を小さくしたかったため,赤い点の
座標の小さい順から考え,ペアを作る事の出来る中で
座標が最小の青い点を選ぶことを繰り返すものであった.
しかしこれでは上手くいかない.文章からも明らかであるが上の状態では座標の情報が一切反映されていない.我々が目指している事は闇雲に外側の点を選ぶのではなく,外側は外側でもなるべく内側によっている点を選ぶことである.もっというとなるべくペア間の距離を短く結ぶことにある.
なぜなら距離が離れれば離れるほどその点はより外側にあるという事になり,ペアを作る効率がよくない.どれだけ(原点から)外側にあるかの度合いを測る尺度として距離があり,その距離の長短とペアが対応している事は興味深い.
イメージにおこすとこのようになる.上の座標が最初に考えたペアの作り方である.見て分かるようにどう考えても効率的でない.
翻って下はどうであろうか.ペア間の距離が短くなっているのもさることながら,何より作成可能なペアの個数が増えている.おそらくこれを目指す事が最善手であると考えた.
ではこのようにするためにはどうすべきであろうか.自分は青い点に注目した.座標の小さい青い点から(外側から),ペアを作成可能な赤い点を探していく手法だ.
そういった中でどれとペアを結ぶべきか.やはりここでも距離が出てくる.距離の計算はで求める事が出来る.そして,今は
座標が小さい方から見ているため,これ以上
座標の距離を縮めようとしてもあまり距離は縮まらない.むしろ注目している青い点に対し,赤い点の
座標がギリギリまで近い点を選ぶことでその距離を最小化出来る.このようにしてGreedyを行うと上手く行くのである.
「あえてはじめは距離が離れているところを選ぶのはありじゃないか.」,と思うかもしれない.しかし,今考えているのはが小さい順である事に注意したい.最初にあえて自分に近い点を選ばず,遠くの点を選んだとしよう.そうした時,次の青い点は[tex;x]座標が離れているぶんもっと遠くなる.そうなってしまった場合,その行為に何の得もない.
また,それによって次のペアの距離が縮まったと仮定しても,その場合はそもそもはじめの青い点は次のペアの赤い点とペアを結べないか,どちらの赤い点も入れ替えてペアを作る事が可能かのどちらかでしかないため,「はじめにあえて距離が離れているものを選ぶ」方針ではGreedyに対し,ペアの数を減らす事さえあっても増やす事はありえない.
加えてGreedyの基本姿勢が「その場での最善」を優先し,それを繰り返す思考であるから「その場での最善」を優先せず,かといって後の方で取り返せる保証のない方針は得策ではない.*1
考えなければならないのは一度ペアに使った点はもう使えないという事.今回は一度ペアになった赤い点の座標を大きくし,彼方に飛ばす事でそれに対応した.
if (k != -1) {
count++;
ab.at(k).at(0) = 2000;
}
青い点はループで全探索するため,ペアの成否を考えなくてよい.扱いやすい.
プログラム
#include <bits/stdc++.h>
using namespace std;
int main() {
int N;
cin >> N;
for (int i = 0; i < N; i++) {
for (int j = 0; j < 2; j++) {
cin >> ab.at(i).at(j);
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < 2; j++) {
cin >> cd.at(i).at(j);
}
}
sort(cd.begin(), cd.end());
int count = 0;
for (int i = 0; i < N; i++) {
int y = -1;
int k = -1;
for (int j = 0; j < N; j++) {
if (cd.at(i).at(0) > ab.at(j).at(0) &&
cd.at(i).at(1) > ab.at(j).at(1) && ab.at(j).at(1) > y) {
y = ab.at(j).at(1);
k = j;
}
}
if (k != -1) {
count++;
ab.at(k).at(0) = 2000;
}
}
cout << count << endl;
}
