drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ 平方分割 二部グラフ Union-Find グラフ シーケンシャルDP DP 個数重複も考慮したナップサックDP DP値を利用して状態復元 AOJ JAG AOJ-ICPC600点 数量が小さいことの活用：総和がNになる整数列の種類数はO(√N) グラフテク:下駄を履かせて負辺除去 AOJ-ICPC JAG春冬コン 均等に分ける そのまま覚えたいシンプル設定の中堅以上の典型問題 中堅以上の典型要素を詰め合わせた教育的問題 思わず解きたくなる興味深い良問 これを解いていたおかげで ARC 099 E - Independence がすぐに思いつけた感はあるかも。むしろ制約的に ARC 099 E の完全上位互換だと言える。 問題へのリンク 問題概要 頂点 辺の無向単純グラフが与えられる。 このグラフが「奇数長のサイクルがない」という状態を保ちつつ、最大本数の辺を追加せよ。最初からそうでない場合は -1 をリターンせよ。 制約 考えたこと 「奇数長のサイクルがない」 ⇔ 「二部グラフ」は今となっては典型。 なので、二部グラフである状態を保ちながら辺を付け加えていく問題。最後は完全二部グラフにすることになる。よって、グラフの連結成分ごとに、どちらを… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2018%2F09%2F29%2F154400" title="AOJ 2370 RabbitWalking (JAG 冬合宿 2010 day3-B) (600 点) - けんちょんの競プロ精進記録" 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.user.blog.st-hatena.com/default_entry_og_image/80936665/1516148889515660 Hatena Blog https://hatena.blog 2018-09-29 15:44:00 rich https://drken1215.hatenablog.com/entry/2018/09/29/154400 1.0 100%