ARC092 C : 2D Plane 2N Points(400)
作成日：2018.08.15
最終更新日：2018.08.15
問題概要
二次元平面上に赤い点と青い点が$N$個ずつあり、$i$個目の赤い点、青い点の座標はそれぞれ$(a_i , b_i)$、$(c_i , d_i)$である。
$a_i < c_j$かつ$b_i < d_j$となる色が異なる二つの点をペアにしていく時、最大で何組のペアができるかを求めよ。
但し、1つの点が複数のペアに属することはない。
制約
$1 \leq N \leq 100$
$0 \leq a_i , b_i , c_i , d_i \lt 2N$
$x$座標や$y$座標が同じ点は存在しない
考え方
点を$x$座標が小さい順に見ていくことにする。
青い点を見た時にそれがペアを作れるのは、これまで見た赤い点のうち$y$座標が青い点よりも小さいものである。
また赤い点は$y$座標が小さいほど他の青い点とペアを作りやすいから、青い点とペアとするのは条件を満たすもののうち$y$座標が最も大きいものとして良い。
このようにして選んだ赤い点とペアを作らないとしても、1つの点が複数のペアに属することはないからペアの数は増えない。
以上より、青い点を$x$座標が小さい順に見ていき、ペアにできる赤い点があればその中で$y$座標が最大のものを選びペアにするという貪欲法で解くことができること分かる。
ソースコード
マクロ等はこちら
const int MC = 111;
int N;
P2 r[MC],b[MC];
bool c[MC*2];
int main(){
cin >> N;
repp(i,0,N){
int x,y;
cin >> x >> y;
r[i] = MP(x,y);
}
repp(i,0,N){
int x,y;
cin >> x >> y;
b[i] = MP(x,y);
}
sort(r,r+N); sort(b,b+N);
int ans = 0;
int pr = 0 , pb = 0;
r[N] = b[N] = MP(1234567,1234567);
while(pr < N || pb < N){
if(r[pr].first < b[pb].first){
c[r[pr].second] = 1;
++pr;
} else {
repm(k,b[pb].second-1,-1){
if(c[k]){
c[k] = 0;
++ans;
break;
}
}
++pb;
}
}
cout << ans << endl;
return 0;
}解法まとめ
青い点を$x$座標が小さい順に見ていき、ペアにできる赤い点があればその中で$y$座標が最大のものを選びペアにする。(18-37行)