2019年5月22日水曜日

ABC 017 D - サプリメント

ABC 017 D - サプリメント

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

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

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

S(x)=S(x1)+g(x)=S(x1)+iλ(x1)x1g(i)=S(x1)+S(x1)S(λ(x1)1)=2S(x1)S(λ(x1)1) \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)=0S(-1)=0とする。)したがって、SSに関してDPすればg(N)=S(N)S(N1)g(N) = S(N) - S(N-1)O(N){\mathcal O}(N)で求まることになる。

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