ABC091 C - 2D Plane 2N Points

問題
提出コード

解法

2次元のままこの問題を考えると、いろいろと大変なことになるので、どちらか片方の条件を無視してよくなるような条件を探します。
すると、赤の点と青の点を同時にの昇順、の昇順の優先度でソートを行うと、番目の赤い点と、番目の青い点について、が成立しているときに、については常に条件を満たすようになります。
ということで、この後は次のような問題に置き換えることができます。

• かつ、となる赤い点と、青い点のペアの個数の最大値はいくつか。

制約を見ると、点の個数はとても少ないので、探索にそこそこ時間をかけても大丈夫です。
ということで、上のソート済みの数列に対して前から順番に見ていき、次のような操作をします。

• 次に見る点が赤い点だった場合
  別のリストに、赤い点を記録していく。

• 次に見る点が青い点だった場合
  赤い点を記録したリストをについて昇順にソートしなおし、より小さいのうち、が最大となっている点を二分探索で調べる。その点と、をペアにする(リストからの点を消す)。

が小さい順に青い点を持ってきたときに、まだペアになっていないかつ、今見ている青い点とペアを組める赤い点のなかから1つペアを組むとしたら、組める中でが最も大きいものを選んだ方が得になるので、青い点を取ってくるたびに二分探索でそのような点を探します。
ということで、これを繰り返し、完成したペアの個数が答えになります。

感想

これ、400点にしても難しい気がします…
たしかにやっていること自体は400点っぽい内容なのでなんともいえないです。
初見のときは解けなかったのですが、今回もかなり時間がかかりました。完全に点の個数がぐらいあると思っていたので、ソートした後どうやってペアをつくればいいかずっと悩んでいました。