hotpepsiの練習帳

SRM 691

17:34

https://competitiveprogramming.info/topcoder/srm/round/16730/div/1

Div1 Easy (300) Sunnygraphs

問題

• 0～N-1までのN個の頂点がある
• 各頂点iは、頂点a[i]と辺を持つ
• 0本以上の任意の辺を頂点Nとつなぎ直すとき、頂点0と1が連結である場合の総数を求める

方針

• (終了後)
• pekempeyさんの解説を読む
• 0から行ける頂点に1、1から行ける頂点に2をORしていく
• 値が0,1,2,3の頂点をそれぞれw,x,y,zとする
• (1)xをNにつなぎかえるとき(2)yをつなぎかえるとき(3)xとyをつなぎかえるとき(4)xとyをつなぎかえないとき、それぞれで計算して、最後に2^w倍する(wの状態は連結に無関係なので全ての場合がありうる)
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_691/Sunnygraphs.cpp

結果

--- 0pt 118th/411 rating 1523 -> 1510 (-13)

これは全く手が出なかったが、コードはシンプル。

http://togetter.com/li/981500