人権なし

青コーダーの競プロで解いた問題や開発の進捗などの記録です

Educational DP Contest:P - Independent Set

問題

atcoder.jp

解法

dp(i, f) := 頂点 i を黒で塗れるかどうかが f のとき,頂点 i から到達できる頂点を塗り分ける通り数

と定義する.このとき,

dp(i, f) = dp(v_1, true) * dp(v_2, true) * ... (f == false のとき)

dp(i, f) = dp(v_1, false) * dp(v_2, false) * ... + dp(v_1, true) * dp(v_2, true) * ... (f == true のとき)

(v は頂点 i から直接行ける頂点)

と漸化式が立つ.状態数 O(N),遷移 O(N) だけれども,各辺は1回しか見ないので O(N + N).

解答

atcoder.jp

実装に関して,無限ループを避けるため,親の頂点を dp の引数に持ちながら dp すればよい.

f:id:babcs2035:20190107173548p:plain