AtCoder Regular Contest 092 C - 2D Plane 2N Points

お題箱より。

以前の自分が解法の正当性を理解するのにすごく悩んだ問題で、印象深いです。

解法

考察

2次元の座標点を扱う際には「平面走査」というテクニックがよく使われます。これは座標点をある一方の座標、例えば $x$ 座標でソートして小さい順番に見ていき、もう一方の $y$ 座標についてはデータ構造などを用いて処理していくテクニックです。軸に平行な直線をスライドさせて平面全体を走査していくので、Codeforcesなどの英語解説では「scanline algorithm」と書かれたりします。

f:id:betrue12:20200907223931p:plain

また赤と青、左端と右端など2種類の要素をペアにする問題では、平面走査や数列の走査と合わせて以下のテクニックがよく使われます。

赤い点が登場したら、その点を「ペア待ち点の集合」に入れる。
青い点が登場したら、ペア待ち点の中から最適な頂点とペアを作る。

このとき「青い点が登場したときに、その都度（何らかの基準で）最適な赤い点を選んでペアにする」という方法が存在して、かつそれが全体最適であることが証明できる場合、正しい解法として成立します。今回の問題の場合はどうか、考えてみましょう。

まず $x$ 座標でソートして小さい順番に見ていった場合、ペアにする2点が赤い点→青い点の順番に登場することが、 $x$ 座標についての条件を満たす必要十分条件になります。つまり $x$ 座標についての条件は自動的に解決し、今後考慮する必要がなくなります。

赤い点が登場したら、その点を「ペア待ち点の集合」に入れます。青い点が登場した時にとり得る選択肢は

ペア待ちになっている赤い点のどれか1つとペアにする。
どの赤い点ともペアにしない。

の2通りです。ここでもしペアにする場合は、ペアにできる条件を満たす点の中で最も「今後使いにくい」点を使ってしまうのが最適です。赤い点は $y$ 座標が小さいほうがペアにしやすいので、選ぶのは「青い点の $y$ 座標よりも小さいもののうち、最も $y$ 座標が大きいもの」になります。

一方ペアにできる赤い点が存在するのに「あえてペアにしない」という選択も考えられますが、この選択は絶対に得にはならないことが証明できます。ペアにしないことを選んだ時点で1つペア数を損していて、この赤い点1つを温存したことによって今後2ペア以上のアドバンテージを得られることはないからです。

証明は以下のようにできます。あえてペアにしないことで温存した赤い点を $p$ として、その後 $p$ を残した場合の最適なペアの作り方を考えます。このペア構成に $p$ が使われていれば、そのペアを1つ解消することで $p$ を使わないペアの作り方が得られます。また使われていない場合は $p$ が無くても同一数のペアが作れます。つまり $p$ の有無でその後作られる最適なペア数は高々1つしか変わらないことが示されました。

これまでの考察により、以下のアルゴリズムで最適解が得られることが分かりました。

まず全ての点を $x$ 座標でソートする。
点を順番に見ていきながら、以下の処理をする。
- 赤い点 $(a_{i}, b_{i})$ が登場したら、その $y$ 座標 $b_{i}$ を「ペア待ち点の $y$ 座標の集合」に入れる。
- 青い点 $(c_{i}, d_{i})$ が登場したら、ペア待ち点の中で「 $y$ 座標が $d_{i}$ より小さいものの中で最も大きいもの」を探し、存在するならばペアにする。

実装

実装ですが、実現したい計算量に応じていくつかの方針があります。今回の場合点の個数が $100$ 以下かつ座標値も $200$ 未満なので、配列などで管理して全部の座標値を見ていく方針で良いです。

$Y\lbrack b\rbrack$ を「ペア待ち点の $y$ 座標の集合に値 $b$ が含まれていたらtrue、そうでなければfalse」である配列とします。まず座標点を $x$ 座標で全てソートして順番に見ていきます。赤い点 $(a_{i}, b_{i})$ が登場したら $Y\lbrack b_{i}\rbrack$ をtrueにします。青い点 $(c_{i}, d_{i})$ が登場したら $Y\lbrack d_{i}-1\rbrack$ から下に順番に見ていって、trueであるものが見つかったらペアにする、つまり答えに1加算してその値をfalseにすれば良いです。