目的
ABC412のD問題。
インプットにより作成した無向グラフを、全て次数2にするには辺を最低何本追加したり削除すればいいか、というような問い。
点の数N<=8の意味を考えず解法を考えるとACにたどり着けなかった。
制約から解法を考えることが大事だと思ったのでメモ。
環境
Windows、pycharmでコード作成
pypyで提出
自分の間違った解法
作成したグラフからベストな次数2のグラフを導き出せると予想。
dfsでグラフを閉路ごとに分けて、閉路のどこかの辺を切ってから別の閉路とつないで・・・と操作しようとしたがうまく書けず。
解説をもとに作った解法
与えられた点の数Nから、次数2になるグラフを全パターン洗い出す。
それぞれのパターンと、インプットのグラフの差分が操作数。
最小の操作数が答え。
点が6個以上あるときは閉路が2つのときのパターンも考慮する。
今後はこう考える
制約が少なければまず全探索。
最後に
制約大事。
競技プログラミング面白い。