Xmas Contest 2017 F問題 Tree Disassembly 解説

問題 | 解説まとめ

1~5は全探索ができる大きさのランダムケース、6~10は大きいけれどそれぞれなんらかの性質を持ったグラフとなっています。
手元で全ての答えを計算して埋め込めばいいですね。Nが全ての入力で異なるので、ケースの特定も簡単です。

1~5

1は手計算でも頑張ればできるかも。
2は各辺について色を全通り試して判定しても間に合います。
3以降はちゃんと枝刈り探索などを書かないと厳しいと思います。

想定解は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

f:id:snuke:20171226144116p:plain
K4が頂点どうしで繋がって木っぽくなっています。
この問題の性質を考えると、関節点で分離して独立に解いて掛け合わせると良いことが分かるので、K4の答え12を33乗すれば良いです。

7

f:id:snuke:20171226144752p:plain
幅2の管状になっていて木幅が小さいので列単位で適当なDPをすれば解けます。
実際に考えて見ると、実は状態は「片方の色が繋がっててもう一方が繋がってない」の実質1通りしかないので、単に2*6^50が答えになります。

8

f:id:snuke:20171226145433p:plain
これを見ても104の次数が高そうなことくらいしかわからないので、graphvisの方の画像を見た方がいいですが、サイズがデカすぎるので載せないでおきます。
f:id:snuke:20171226145439p:plain
代わりに、小さい版を作ってビジュアライズしました。
こんな感じで多角錐みたいになってます。
N=4から実験して見ると、12,28,60,124,252...となっていて、これは2^N-4です。
なぜこうなるかを考えてみると、周りの輪っかの辺の色を決めると、全部同じ色の時以外はスポークの辺の配色が2通り存在するので(2^(N-1)-2)*2という感じ。
f:id:snuke:20171226153239p:plain

9

f:id:snuke:20171226154355p:plain
なんか投網みたいな形です。
良く考えると輪っかサイズが10になった08.txtを10個繋げたのと同じ状況なので、(2^11-4)^10が答えです。

10

f:id:snuke:20171226155051p:plain
これもgraphvisの方が見やすいです。
f:id:snuke:20171226155049p:plain
グリッドの最後をK4で帳尻合わせた形になっています。
この問題の性質を考えると、次数2の頂点は片方が赤でもう片方が青になるだけなので、答えを2倍して取り除いても同じだということがわかります。それを隅から順番にやっていくとK4が最後に残り、(2^99)*12が答えであることがわかります。