人権なし

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

CODE THANKS FESTIVAL 2018:E - Union

問題

atcoder.jp

解法

dp(i, j) := 整数 i が j 個あるとき,これから黒板に書かれている数を1つにする通り数

と DP を定義する.このとき,

dp(i, j) = dp(i + 1, (j + k) / 2)

(k は 0 <= k <= a_i で (j + k) % 2 == 0 を満たす整数)

と漸化式が立つ.i が T を超えた場合,上の漸化式だと愚直に / 2 していく形になって虚無なので,その時の j が2の累乗数であれば 1 通り,そうでなければ 0 通りとして枝刈りしてしまえばよい.O(T * 300^2).

解答

atcoder.jp

計算量的には枝刈りは必要なかったが,実装上したほうが楽だと思った.

f:id:babcs2035:20181230170648p:plain