snuke https://blog.hatena.ne.jp/snuke/ あなたは嘘つきですかと聞かれたら「YES」と答えるブログ https://snuke.hatenablog.com/ Algorithm 競プロ ARC092C - 2D Plane 2N Pointsの証明が話題になってたっぽいので問題を見てみたら、最大マッチング系貪欲の証明テクが詰まった問題だなぁと思ったので書いてみた。 問題概要 平面上に赤い点と青い点がある。 赤い点が青い点の左下である（つまりxもyも小さい）とき、それらはペアにできる 何ペア作れるか 解法 青い点をxの昇順に見て、マッチングできる赤い点があればそのうちyが最大のものとマッチングさせていく貪欲。 証明テク１：マッチングできるときはしてもよい つまり、あえてマッチングさせないことによって答えが増えることはない。なぜなら、ある青い点 A と赤い点 X をマッチングでき… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fsnuke.hatenablog.com%2Fentry%2F2019%2F01%2F04%2F004133" title="最大マッチングを貪欲する問題の証明典型テク - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/s/snuke/20190103/20190103234249.png Hatena Blog https://hatena.blog 2019-01-04 00:41:33 rich https://snuke.hatenablog.com/entry/2019/01/04/004133 1.0 100%