pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

TopCoder SRM 691 (Div. 2) Medium. Sunnygraphs2

問題

n 頂点のグラフがある。各頂点 i に対して、

  • i から a[i] に辺を張る
  • i から n に辺を張る

のどちらかを選択できる。このようにして作られた 2n 通りのグラフのうち、0..n-1 が連結であるようなものの個数を求めよ。

  • 1≦n≦50

解法

i から a[i] に普通に辺を張ってみる。このとき矢印を辿ると必ずサイクルに辿り着く。

f:id:pekempey:20160531044940p:plain

サイクル外の頂点を一個切り離してみる。これだと非連結になってしまう。

f:id:pekempey:20160531044954p:plain

非連結を解消するにはサイクル内の頂点を 1 個切り離すしかない。

f:id:pekempey:20160531045001p:plain

サイクル内の頂点を 2 個切り離しても連結のままである。

f:id:pekempey:20160531045314p:plain

一個でもサイクル内の頂点を切り離していれば、サイクル外の頂点を切り離しても連結のままである。

f:id:pekempey:20160531045005p:plain

サイクル外の頂点数を x、サイクル内の頂点数を y とする。

f:id:pekempey:20160531045008p:plain

ここまで分かれば求め方も分かるだろう。x を切り離すか、切り離さないかで場合分けする。

(1) x を切り離すとき
x の切り離し方が 2x -1 通り、y の切り離し方が 2y -1 通りなので$(2^x-1)(2^y-1)$ 通り

(2) x を切り離さないとき
y は切っても切らなくてもいいので $ 2^y $ 通り。

最初から連結の場合しか考えてなかったが、当然最初から連結でないものもある。

f:id:pekempey:20160531050236p:plain

こういうときは x も y も切り離さないパターンを除外する必要がある。といっても -1 するだけなので大したことはない。

TopCoder SRM 691 (Div. 2) Medium. Sunnygraphs2

Div.2 med にしては難しくない…?