ABC 017 D - サプリメント

• 問題
• AC

サプリメントの番号を0-basedで$0, ..., N-1$として考える。与えられた条件に従ってサプリメント$0, ..., x-1$を摂取するときの場合の数を$g(x)$とする。サプリメント$x$と同じ日に摂取できるサプリメントの番号で最小のものを$\lambda(x)$とすると、$g(x)$の漸化式は

$\begin{aligned} g(0) & = 1 \\ g(x) & = g(x-1) + g(x-2) + ... + g(\lambda(x-1)) \end{aligned}$

と書ける。$\lambda(x)$のテーブルはいわゆるしゃくとり法で作れるので、漸化式にしたがってDPすれば答えは求まる。ただ、素朴に遷移すると$\mathcal{O}(N^2)$になって間に合わない。そこで、$g$の累積和を考えることにする。$S(x) := \sum_{i=0}^xg(i)$とすると

$\begin{aligned} S(x) & = S(x-1) + g(x) \\ & = S(x-1) + \sum_{i \in \lambda(x-1)}^{x-1}g(i) \\ & = S(x-1) + S(x-1) - S(\lambda(x-1)-1) \\ & = 2S(x-1) - S(\lambda(x-1)-1) \end{aligned}$

（ただし、$S(-1)=0$とする。）したがって、$S$に関してDPすれば$g(N) = S(N) - S(N-1)$が${\mathcal O}(N)$で求まることになる。

DPのやり方はすぐにわかったのだが、$\lambda(x)$は番号$x$と同じ種類のサプリメントを見つけるまで戻れると思ってしまってWAした。