CODE FESTIVAL 2018 qualA C問題 : 半分

問題. 半分

非負整数列  A_1, \ldots, A_n と非負整数  K が与えられる.数列にちょうど  K 回の操作を行ったあとの数列としてありうるものの個数を求めよ.ただし,各操作とは  1 \le i \le n 番目の要素を 2 で割った商の小数点以下切り捨てた値に置き換えることである.

制約 1 \le n \le 50,  0 \le A_i \le 10^{18},  0 \le K \le 10^9

解法. 動的計画法

解けなかったので解説 [1] を参考にした.

 c(i) を,  A_i を 0 にするのに行った操作の回数とする.このとき,1回の操作で要素の値は半分となるので,各要素に対して高々60回の操作しか行わない.
操作を行ったあとの数列の個数を動的計画法で求めることを考える. f(i, j) を部分列  A_1, A_2, \ldots, A_i に対してちょうど  j 回操作を行った後の数列としてありうるものの個数,として漸化式を考えたいが上手くいかない.なぜならば,要素0に対しても操作が行えて,操作後の数列が変らないので,操作の回数が異なっても同じ数列を数えている場合があるからである.したがって,操作後の数列で0を含むものと含まないものを分けて数えてみることにする.
  f_1(i, j) := 部分列  A_1, \ldots, A_i でちょうど  j 回操作を行って,要素に0を含まない数列の個数
  f_2(i, j) := 〃 ,少なくとも1つの要素に0を含む数列の個数(ただし,0の要素はこれ以上操作を行わない)
先程とは異なり,このように定義すると操作の回数が異なっていると異なる数列を数えていることになる.また, f_2 で0の要素に対して操作を行わないようにしたのも,異なる数列を数えられるようにしたためである.
 1 \le i \le n 0 \le j \le \sum_{k=1}^{i} c(i) に対して漸化式を考える.ただし, f_1(0, 0) := 1 とする.漸化式は,
  f_1(i, j) := \sum_{j - c(i) + 1 \le j' \le j} f_1(i - 1, j')
  f_2(i, j) := f_1(i - 1, j - c(i)) + \sum_{j - c(i) \le j' \le j} f_2(i - 1, j')
となる. f_2 の右辺は,0を含まない列と含む列に  A_i に操作を行ったものを加えた数列を数えている. S = \sum_{i=1}^{n} c(i) とすると,上の漸化式から  S \le j に対しては  f_1(i, j) = f_2(i, j) = 0 となるので,答えは,
  f_1(n, K) + \sum_{i = 0}^{\min(S, K)} f_2(n, i)
となる.

計算時間 O(n^2 (\log A)^2) ( A は数列の要素の最大値)

まとめ

状態をどう定義すればいいのかが分からなかったので残念.
「異なる状態で同じものを数えてしまっている場合は状態を変える」を意識する.