Tenka1 Programmer Contest 2019 F - Banned X

F - Banned X

気合いで数える問題。ARC-FやAGC-Dあたりの数え上げをやりまくったおかげで解けたかな…と思います。

解法

まず、全要素の合計が $X$ 未満かどうかで場合分けをします。

合計が $X$ 未満である場合

要素の合計が $X$ 未満である場合はどのように数を並べてもよいです。このような場合の数は以下のようなDPで求められます。

$dp\lbrack i \rbrack\lbrack j \rbrack =$ 各要素の値を $0, 1, 2$ から選ぶことにして、 $i$ 個目までの値を決めて、合計が $j$ であるような場合の数

このDPを計算して $j \lt X$ の範囲における $dp\lbrack N \rbrack\lbrack j \rbrack$ を全部合計すれば、要素の合計が $X$ 未満であるような場合の数が求められます。

※後で必要になる「各要素の値を $1, 2$ から選ぶことにしたときの場合の数」を利用して計算することもできます。

合計が $X$ を超える場合

合計が $X$ 以上の場合を考えます。ただし $X$ ぴったりになってはいけないので、 $X$ を超える場合を考えます。

$0, 1, 2$ を並べた数列の代わりに、その累積和を前から並べた数列を考えます。そしていったん $0$ は考えないことにして、狭義の単調増加になっている累積和の列を考えます。

このとき、累積和が $X$ を超えるタイミングでは $X-1$ から $X+1$ へのジャンプが起こっているはずです。そして $X+1$ が存在するので $1$ が存在してはいけません。なので累積和の並びは、

$0, 2, ..., X-1, X+1, ...$

となっているはずです。

$X+1$ の先はどうなるでしょうか。 $2$ があるので $X+2$ を作ってはいけません。なので $X+1$ から増えるとすれば $X+3$ にまたジャンプしないといけません。そして $3$ が存在してはいけないので、

$0, 2, 4, ..., X-1, X+1, X+3, ...$

となるはずです。

ここから規則性が掴めます。ある正の奇数を $y$ として、数列の最大値が $X + y$ であるとします。そのとき部分和に $X$ が現れない条件は、累積和の数列について

からまでは全て2ずつ増加する。
- この過程で $X$ が出現してはいけない。つまり $X$ が偶数でかつ $X \le y+1$ のときはNG。
$y+1$ から $X-1$ までは自由に増加して良い。（ $y+1 \lt X-1$ のとき）
からまでは全て2ずつ増加する。
- $X$ が奇数で $y+1 \ge X-1$ のときは、これは1. の範囲と重なるので、単に $0$ から $X+y$ まで2ずつ増加するような数列になる。

と書き下すことができます。

さて、累積和がこのような条件を満たすような元の数列の個数を数えましょう。このとき $0$ の存在が厄介で、上記のどのパートにも途中で $0$ が入ってくる可能性があります。そのため「まずは $1, 2$ だけで条件を満たす数列を作った後、 $N$ 個に足りない個数だけ $0$ を追加する」という作戦でいきます。