問題

https://atcoder.jp/contests/arc058/tasks/arc058_c

考え方

考えていたこと

条件を満たす数列はどのような数列であるか考えた。

$x, y, z, w$ を全探索する。そのとき $[x, y-1], [y, z-1], [z, w-1]$ の区間の長さを求めておいて、各区間の長さの要素の和が $X, Y, Z$ なる要素の組み合わせを考えると、これは重複組合せで求めることができる。範囲に含まれない要素は $[1, 10]$ の任意の数を選択できる...

みたいな考察を進めていた。がサンプル3で合わず。よく考えると、範囲外の要素で XYZ の数列が含まれるので数列を重複して数えていることになる。

解説見た

余事象の数え上げを考える。余事象のほうが数え上げやすいため。数列の要素ごとに左から全探索していくことを考える。例えば $X=1, Y=2, Z=1$ という XYZ の組み合わせを考えると、X Y が決まっていたとすると、どういうときに次の数 Z を選べないか。

それまでの数字の和が 1 2 となる場合は次に Z として 1 をとることはできない。 XYZ が 121 になってしまうため。

数列の状態を bit で考えることにしよう。 $X+Y+Z \le 17$ であるから $2^{X+Y+Z} \le 2^{17} \approx 1.3 * 10^5$ として状態を持つことができる。

今までの数列の和の状態が左から 1 2 となる場合に bit として $110$ となっているとしよう。このように bit で状態をもつことを考えることがこの問題を bitDP で解くために重要な考察な気がする。このとき $Z$ として $1$ をとることを考えると bit の状態は $1101$ となる。これは bit の下位(0-indexed)から考えて $Z=1, Y=2, X=1$ となっているので状態として遷移することができない。そうでない場合、例えば $Z=3$ などを選ぶ場合は $110100$ となるので遷移することができる。

よって次のようなメモ化全探索を考えよう

$f(i, state) := i$ 桁目まで考えて数列の状態が $state$ であるような場合の数

DP遷移は $i$ 桁目に数 $j$ をとるとすると next = state << j | 1 << j - 1 となる(実装のまんま)。これが XYZ にならないとき、つまり next >> z - 1 && next >> y + z - 1 && next >> x + y + z - 1 にならないときのみ遷移可能