Australia

ウォンバットのブログ

CODE FESTIVAL 2018 qual A C - 半分

問題

https://beta.atcoder.jp/contests/code-festival-2018-quala/tasks/code_festival_2018_quala_c

解法

$A_i=0$ になったら、それ以降は $2$ で割らないものとします。そうすると、求める答えは本来の「 $K$ 回の操作後の数列としてありうるものの個数」に「 $K$ 回未満の操作後の $0$ を $1$ つ以上含む数列としてありうるものの個数」を加えたものになります。

$dp[i][j][k]:=$ $A_1$ から $A_i$ まで考えたときの、 $j$ 回操作してできる数列の個数（ $k$ はそれまでの要素に $0$ があったかどうかのフラグ）

というDPを考えれば、 $A_i$ を $2$ で $c_i$ 回割ると $0$ になるとして、

$dp[i][j][0]=\displaystyle \sum_{j'=j-c_i+1}^{j} dp[i-1][j'][0]$
$dp[i][j][1]=\displaystyle \sum_{j'=j-c_i}^{j} dp[i-1][j'][1]+dp[i-1][j-c_i][0]$

と遷移が定義できます。あとはここから適切に値をとってきて足し合わせればよいです。
計算量は $O(N^2 (\log \max A_i)^2)$ になります。

実装

https://beta.atcoder.jp/contests/code-festival-2018-quala/submissions/3243576

反省

DPをDPだと気づくのはけっこう速くなったような気がしますが、詳細を詰めるのが苦手です。