drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ AtCoder AtCoder1200点 AGC-E 二分探索 最大値の最小化 Greedy 最適化の考察：最適解の形を考える 最適化の考察：変形しても悪化しない 最適化の考察：探索候補を絞る 数列 マッチング Greedyなマッチング 区間 天才な二分探索 銅色diff NoviSteps5D 楽しかった。7 時間かかったけど自力 AC できたー！ 問題へのリンク 問題概要 正の整数 が与えられる。 個の 以上 未満の整数 を 個ずつのペアに分けたい。 各ペア に対して % の値 (これを醜さと呼ぶ) を求め、その最大値をとる。 この最大値の最小値を求めよ。 制約 考えたこと 一見して、「最大値の最小化」なので、二分探索に思えるけど、最終的にはそういう枠組で二分探索を使うわけじゃないのが面白い。 とかだったら、二分探索して、醜さが mid 以下となるペアのみで完全マッチングが作れるかを一般マッチングライブラリで殴る解法が成立する。 今回はそんなことできないので、何かしら Greedy… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2019%2F04%2F28%2F100000" title="AtCoder AGC 032 E - Modulo Pairing (5D, 銅色, 1200 点) - けんちょんの競プロ精進記録" 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/d/drken1215/20190428/20190428095226.png Hatena Blog https://hatena.blog 2019-04-28 10:00:00 rich https://drken1215.hatenablog.com/entry/2019/04/28/100000 1.0 100%