1~5は全探索ができる大きさのランダムケース、6~10は大きいけれどそれぞれなんらかの性質を持ったグラフとなっています。
手元で全ての答えを計算して埋め込めばいいですね。Nが全ての入力で異なるので、ケースの特定も簡単です。
1~5
1は手計算でも頑張ればできるかも。
2は各辺について色を全通り試して判定しても間に合います。
3以降はちゃんと枝刈り探索などを書かないと厳しいと思います。
次数 3 以下の点は必ず存在して，次数 2 なら単に消して答えを 2 倍にすればよくて，次数 3 ならその点まわりのつなぎ方は 3 通りなので全部試して再帰できて，これをやると 70 点
— 準急くき (@semiexp) 2017年12月24日
想定解は「graphillionで殴る」です。
グラフの列挙したりするのが得意なライブラリです。
辺に重みをつけて重みを最大化/最小化する問題なんかも解けます。
数え上げおねえさんを救うために開発された(page3)ライブラリで、はなく(page4)、ZDDを使ったすごいやつです。強い。
パスの他にもサイクルや木や森やクリークや...といろんなグラフが扱えるし、それらを組み合わせたものを列挙みたいなこともできます。結構いろいろできます。
例えば今回の問題の1~5は以下のコードで解けます。
from graphillion import GraphSet def read(): return map(int, raw_input().split()) n = read()[0] edges = [tuple(read()) for i in range(2,n*2)] GraphSet.set_universe(edges) trees = GraphSet.trees(is_spanning=True) comps = trees.complement() ans = comps&trees print(len(ans) % (10**9+7))
こういうアルゴリズム系のライブラリはpythonが結構多いのでpython書けるとだいぶいい感じです。
やってることとしては、辺をタプルで持ったリストを作って、それをグラフに登録し、全域木(trees)を列挙し、その補グラフ(comps)を列挙し、それらの積集合を取ってそのサイズを求めています。
"列挙"と言っても、全部を実際に列挙しているわけではなく、実態としては条件を満たす集合の圧縮表現を構築しているだけで、かなり速いです。
自分はまだあまり使いこなせてはいませんが、それですらかなり強力なライブラリだと思うのでオススメです。
6~10
6~10はそれぞれのグラフをビジュアライズするとどんなグラフかが見えると思います。
グラフのビジュアライズはgraphvisやjs製のそれっぽいライブラリを使うと良いでしょう。
僕はこのサイトをよく使います。（超便利、EMKさんありがとうございます）
6
K4が頂点どうしで繋がって木っぽくなっています。
この問題の性質を考えると、関節点で分離して独立に解いて掛け合わせると良いことが分かるので、K4の答え12を33乗すれば良いです。
7
幅２の管状になっていて木幅が小さいので列単位で適当なDPをすれば解けます。
実際に考えて見ると、実は状態は「片方の色が繋がっててもう一方が繋がってない」の実質１通りしかないので、単に2*6^50が答えになります。
8
これを見ても104の次数が高そうなことくらいしかわからないので、graphvisの方の画像を見た方がいいですが、サイズがデカすぎるので載せないでおきます。
代わりに、小さい版を作ってビジュアライズしました。
こんな感じで多角錐みたいになってます。
N=4から実験して見ると、12,28,60,124,252...となっていて、これは2^N-4です。
なぜこうなるかを考えてみると、周りの輪っかの辺の色を決めると、全部同じ色の時以外はスポークの辺の配色が２通り存在するので(2^(N-1)-2)*2という感じ。
9
なんか投網みたいな形です。
良く考えると輪っかサイズが10になった08.txtを10個繋げたのと同じ状況なので、(2^11-4)^10が答えです。
10
これもgraphvisの方が見やすいです。
グリッドの最後をK4で帳尻合わせた形になっています。
この問題の性質を考えると、次数２の頂点は片方が赤でもう片方が青になるだけなので、答えを２倍して取り除いても同じだということがわかります。それを隅から順番にやっていくとK4が最後に残り、(2^99)*12が答えであることがわかります。
