KokiYamaguchi https://blog.hatena.ne.jp/KokiYamaguchi/ Learning Algorithms https://kokiymgch.hatenablog.com/ Atcoder D - 辺彩色 解法 まず辺に色を塗っていく操作を、逆順から見ていきます。この発想は以下のような問題でも使えます。B - Splatter Paintingそうすると、一回塗った辺はもう変更することができないという操作に変えることができます。すると、各辺は条件を満たしている色でしか通過できないという条件を作ることができ、$DFS$ で普通に探索できます。さて、次に交互に塗っていくという性質から、奇閉路を一つでも作れば、そこからすべての辺を塗っていけることに気づきます。逆に奇閉路が作れない場合は、二部グラフなので、順番に関係なく辺を選んでいけます。すなわち、貪欲に辺を選んでいって、すべての辺を塗… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fkokiymgch.hatenablog.com%2Fentry%2F2018%2F01%2F23%2F125134" title="Atcoder Regular Contest 041 D. 辺彩色 - Learning Algorithms" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2018-01-23 12:51:34 rich https://kokiymgch.hatenablog.com/entry/2018/01/23/125134 1.0 100%