ARC092C - 2D Plane 2N Pointsの証明が話題になってたっぽいので問題を見てみたら、最大マッチング系貪欲の証明テクが詰まった問題だなぁと思ったので書いてみた。
問題概要
- 平面上に赤い点と青い点がある。
- 赤い点が青い点の左下である（つまりxもyも小さい）とき、それらはペアにできる
- 何ペア作れるか
解法
青い点をxの昇順に見て、マッチングできる赤い点があればそのうちyが最大のものとマッチングさせていく貪欲。
証明テク１：マッチングできるときはしてもよい
つまり、あえてマッチングさせないことによって答えが増えることはない。
なぜなら、ある青い点 A と赤い点 X をマッチングできるとき、
- マッチングさせる：残りの点集合から A と X が消える
- メリット：答えが 1 増える
- マッチングさせない：残りの点集合から A が消える
- メリット：X を残せる
で、「X を残せる」ことによって答えは高々 1 しか増やせないため、(マッチングさせたときの答え) < (マッチングさせないときの答え) となることはない。
ただし、A と別の赤い点 Y をマッチングさせる方が答えが良くなるという可能性はある点に注意。
このテクは結構出てくる。
使えるのは以下のようなケースのとき。
- 次数１の頂点がある：木でのマッチングなど
- マッチング相手に全順序がある：後述
例題：最近だとこれとか
証明テクテク２：マッチング相手に最弱の頂点があれば、それとマッチングさせてよい
以下のような状況を例に取って説明します。
緑の線の接続関係は同じとします。（灰色は何でもいい）
今、A にマッチングできる点は X と Y です。
X, Y とマッチングさせられる頂点集合を n(X), n(Y) とすると、n(X) ⊆ n(Y) です。
このとき、A と X はマッチングさせてもいいということです。
（少なくとも X か Y のどちらかとマッチングさせてもいいというのはテク１から言えますね）
なぜなら、
- Y とマッチングさせる：このとき残る辺集合を E とする
- X とマッチングさせる：このとき残る辺集合は(X と Y を区別せずに見ると) E + 辺(Y,α) となる
となり、辺が多い方が当然答えは大きくなるので X とマッチングさせても良いため。
マッチング相手が３頂点以上あった場合でも、その中で n(v) が最弱の頂点があればそれとマッチングさせて良い（つまり、どの他の頂点 u についても n(v) ⊆ n(u) が成り立つ v があれば）
大抵の問題ではマッチング相手の中に全順序があるが、一応そこまでは必要ない。
相性の良い競プロテク１：平面走査で変数を１つ消す
この問題の最後のピースです。
このままだと２変数あるので全順序とかも成り立ってないので工夫が必要です。
"A" として試す青い点を x の昇順で見ていくことによって x を消して１変数にすることができます。
すると y の大小だけの全順序が成り立つようになるわけです。
もう少し詳しく言うと、
- A の x 座標 x_A は残っている青い点のうち最小である
- 以降は x 座標が x_A 以下の赤い点は全部 x 座標が -∞ だと思っても答えは変わらない
- A とマッチングできる頂点は x 座標が -∞ の赤い点のうち y 座標が y_A 以下のものである
- x 座標が -∞ の赤い点の中では、y 座標は大きければ大きいほど "弱い"
ということから、最初に書いたような解法の正当性が示せる。
あとがき
貪欲法の問題は、正しいと確信できる程度の証明までして初めて解けた言えると思うんですが、
証明方法にも典型パターンというものは存在して、そういうのに積極的に触れていけばその内できるようになっていくと思います。
