TopCoder SRM 691 (Div. 1) Easy. Sunnygraphs

問題

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

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

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

• 1≦n≦50

解法

0 から辿れる頂点を x、1 から辿れる頂点を y、0と1の両方から辿れる頂点を z、それ以外を w とする。

もし x を切り離してしまった場合、y か z の中からひとつでも切り離せば 0,1 を連結にできる。

もちろん z と y の中で大量に切っても問題ない。

1. x は切り離し y は切り離さない
2. y を切り離し x は切り離さない
3. x も y も切り離す
4. x も y も切り離さない

という 4 パターンがある。

(1) x は切り離し y は切り離さない
x の選び方が 2^x -1 通り、y の選び方が 1 通り、z は一個切り離さないとダメなので 2^z -1 通り、w はどうでもよくて 2^w 通り。よって $(2^x-1)(2^z-1)2^w$ 通り。

(2) y を切り離し x は切り離さない
x の選び方が 1 通り、y の選び方が 2^y -1 通り、z は一個切り離さないとダメなので 2^z -1 通り、w はどうでもよくて 2^w 通り。よって $(2^y-1)(2^z-1)2^w$ 通り。

(3) x も y も切り離す
x の選び方が 2^x -1 通り、y の選び方が 2^y -1 通り、それ以外はどうでもよくて 2^z+w 通り。よって $(2^x -1)(2^y-1)2^{z+w}$ 通り。

(4) x も y も切り離さない
0と1が非連結の場合は切り離さないと繋がらないので 0 通り。連結の場合 z,w がどうでもいいので $2^{z+w}$ 通り。

図は z がサイクルのときだが、z がパス+サイクルの形でも同じような振る舞いを見せるので問題なし。

TopCoder SRM 691 (Div. 1) Easy. Sunnygraphs

前回に引き続いて場合分けすると死ぬタイプの問題。短時間のコンテストだとどうしても焦ってしまい条件の整理に失敗する。