2019-01-04から1日間の記事一覧

最大マッチングを貪欲する問題の証明典型テク

ARC092C - 2D Plane 2N Pointsの証明が話題になってたっぽいので問題を見てみたら、最大マッチング系貪欲の証明テクが詰まった問題だなぁと思ったので書いてみた。 問題概要 平面上に赤い点と青い点がある。 赤い点が青い点の左下である(つまりxもyも小さい…