AtCoder Beginner Contest 222 D 問題 Between Two Arrays

以下の条件をすべて満たす長さ $N$ の整数列 $C=(c_1, \dots, c_N)$ の個数を求めよ.

$c_1, \dots, c_N$ の順に決めることにすると, $c_i$ のときに, どのような値が可能かは $c_{i-1}$ のみによって決まる. よって, 末項が同じ列はまとめて数え上げることができる.

$\beta:=B_N$ とする. $i=0,1, \dots, N, k=0,1, \dots, \beta$ に対して, ${\rm DP}[i,k$ ] を ,

${\rm DP}[i,k]:=c_1, \dots, c_i まで確定していて, c_i=k であるような列の数$

として計算する.

${\rm DP}[0,k ]=[k=0]=\begin{cases} 1 & (k=0) \\ 0 & (k \neq 0) \end{cases}$

$i>0$ のとき, ${\rm DP}[i,k$ ] を求める. 末項を $k$ にするためには $0 \leq c_{i-1} \leq k$ でなくてはならない. また, $a_i \leq c_i \leq b_i$ という条件に注意すると,

${\rm DP}[i,k]=\begin{cases} \displaystyle \sum_{j=0}^k {\rm DP}[i-1, j] & (a_i \leq k \leq b_j) \\ 0 & ({\rm otherwise}) \end{cases}$

である. この漸化式を愚直に計算しようとすると, 要素数が $O(N \beta)$ で, 更新式が $O(\beta)$ なので, 全体で $O(N \beta^2)$ となり間に合わない.

しかし, 更新の結果が $0$ か, $\displaystyle \sum_{j=0}^\bullet {\rm DP}[i-1, j$ ] という形の式になっていることから, 以下のような配列 $S_{i,k}$ を用意する.

$\displaystyle S_{i,k}=\sum_{j=0}^k {\rm DP}[i,j]$

このとき, $S_{i,0}={\rm DP}[i,0], S_{i,k}=S_{i,k-1}+{\rm DP}[i, k]~(k \geq 1)$ という関係式に注意すると, $S_{i,0}, \dots, S_{i,\beta}$ を $O(\beta)$ で求められ,

${\rm DP}[i,k]=\begin{cases} S_{i-1,k} & (a_i \leq k \leq b_j) \\ 0 & ({\rm otherwise}) \end{cases}$

という更新式で, 各要素を $O(1)$ で求められる.

よって, $S_{i,k}$ を利用することにより, ${\rm DP}[N,k$ ] を計算量 $O(N \beta)$ で求めることができ, $\displaystyle \sum_{k=0}^\beta {\rm DP}[N, k$ ] が求めるべき答えである.

Kazun の競プロ記録