ARC092 2D Plane 2N Points

所見

気づけてもいいレベルの貪欲だけども、最大流のライブラリが全世界に公開されている今なら最大流したほうが早そう

問題概要

グリッド上に赤い点と青い点がある。赤い点の座標を(rx,ry)、青い点の座標を(bx,by)としたとき、rx<bx && ry<byならばその点はペアになることができる。
最大いくつのペアが作れるか。

取った方針

二人組をたくさん作る->二部グラフの最大マッチングなので最大流をすると解ける。
ここ(https://qiita.com/drken/items/e805e3f514acceb87602) が詳しい。
仲良しになれる点の間に赤->青のエッジを張り、始点->赤、青->終点のエッジを張ったグラフの最大流量を求めるとそれが解となる。
実装は例のページ(http://tubo28.me/algorithm/dinic/) にある(最悪)が、add_arcしても容量を初期化できないという罠があるので気を付けて使う。

正しい方針(解説の方針)

貪欲をする。
具体的には、青い点のうち、x座標が一番小さいものについて、それよりx座標が小さい中で最もy座標が大きいものを割り当てていく。
厳密な証明は公式解説にあるが、直感的ではある。満たせる中で一番強い条件のものを消費していく、みたいな。
これを証明コミでコンテスト中に思いつけるかというと(^～^)

得られた知見

・二人組をたくさんつくる->最大流

解くのに必要な要素

・最大流
・貪欲でいけるのでは？と思う心

周辺調査によって得られた知見

なし