競技プログラミング用 知識集積所
ABC412D - Make 2-Regular Graph
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
nが8以下と小さいので、作れるサイクルのパターンを全探索（未作成）しても余裕で間に合う。
目標のサイクルを決めたら、元のグラフと目標のグラフの片方だけにある辺の本数を数えればよい。
これはset（未作成）のset_symmetric_difference()を使えばいい。
（辺の情報をpairで持ってもいいし、重複しないようにハッシュ化してもよい）
目標のサイクルを決めたら、元のグラフと目標のグラフの片方だけにある辺の本数を数えればよい。
これはset（未作成）のset_symmetric_difference()を使えばいい。
（辺の情報をpairで持ってもいいし、重複しないようにハッシュ化してもよい）
問題は、サイクルの全探索（未作成）をどのように行うかに工夫が必要なところ。
全体を1つのサイクルにするものの探索は、順列全探索（未作成）をすればよい。
スタート地点n通りと回る方向2通りで2*n回ずつ同じものをダブって確認することになるが、せいぜい16倍なので見なかったことにする。
（気になるなら、最初を1固定にすれば、回転方向の2通りで済む）
スタート地点n通りと回る方向2通りで2*n回ずつ同じものをダブって確認することになるが、せいぜい16倍なので見なかったことにする。
（気になるなら、最初を1固定にすれば、回転方向の2通りで済む）
2つのサイクルにするものの探索は、順列を途中で切ればよい。
前後それぞれ最低でも3つ以上の要素が残るように切る位置を決める、その決め方をループで全部調べればよい。
前後それぞれ最低でも3つ以上の要素が残るように切る位置を決める、その決め方をループで全部調べればよい。
最大の場合でも8!*(1+3)=161280パターンの探索で終わる。
よって、1つのループの中で毎回set_symmetric_differenceを最大28要素の集合にかける余裕は十分にある。
よって、1つのループの中で毎回set_symmetric_differenceを最大28要素の集合にかける余裕は十分にある。
