ARC 028 D - 注文の多い高橋商店

• 問題
• AC

とりあえず「簡単すぎる」ほうの問題を解く。$\mathrm{dp}[x][y] :=$商品を最初の$x$種類からちょうど$y$個選ぶ方法の総数、とする。$\mathrm{dp}[x][y] = d[x-1][y] + \mathrm{dp}[x-1][y-1] + ... + \mathrm{dp}[x-1][y-a_{x}]$と遷移できるが、これでは間に合わないので累積和を考える。つまり$\mathrm{DP}[x][y] :=$商品を最初の$x$種類から$y$個以下選ぶ方法の総数としたとき、

$$\mathrm{DP}[x][y] = \mathrm{dp}[x][0]+ \mathrm{dp}[x][1] + ... + \mathrm{dp}[x][y]$$ $$\mathrm{DP}[x][y] = \mathrm{DP}[x][y-1] + \mathrm{dp}[x][y]$$ $$\mathrm{dp}[x][y] = \mathrm{DP}[x-1][y] - \mathrm{DP}[x-1][y-a_x-1]$$

が成り立つので、

$$\mathrm{DP}[x][y] = \mathrm{DP}[x][y-1] + \mathrm{DP}[x-1][y] - \mathrm{DP}[x-1][y-a_x-1]$$

という${O}(1)$の遷移を導ける。ここから$y$を一個ずらした漸化式$\mathrm{DP}[x][y-1] = \mathrm{DP}[x][y-2] + \mathrm{DP}[x-1][y-1] - \mathrm{DP}[x-1][y-a_x-2]$を引くと、$\mathrm{dp}$についても同じ形の漸化式が得られる:

$$\mathrm{dp}[x][y] = \mathrm{dp}[x][y-1] + \mathrm{dp}[x-1][y] - \mathrm{dp}[x-1][y-a_x-1]$$

これで簡単なほうの問題が解けた。

さて、ここで$N$番目の商品と$i$番目の商品を入れ替えて同じDPをすることを考える。この配列を$\mathrm{dp}_i$とするとき、$\mathrm{dp}_i$は$\mathrm{dp}$と同じ遷移で求まり、しかも$N$種類の商品を処理すると同じ値になるはずである。つまり、任意の個数$y$について$\mathrm{dp}[N][y] = \mathrm{dp}_i[N][y]$が成り立つ。したがって

$$\mathrm{dp}_i[N][y] = \mathrm{dp}_i[N][y-1] + \mathrm{dp}_i[N-1][y] - \mathrm{dp}_i[N-1][y-a_i-1]$$

という等式から

$$\mathrm{dp}[N][y] = \mathrm{dp}[N][y-1] + \mathrm{dp}_i[N-1][y] - \mathrm{dp}_i[N-1][y-a_i-1]$$

が導け、整理すると

$$\mathrm{dp}_i[N-1][y] = \mathrm{dp}[N][y] - \mathrm{dp}[N][y-1] + \mathrm{dp}_i[N-1][y-a_i-1]$$

となる。$i$番目の商品を除いた場合に全体でちょうど$y$個の商品を選ぶ方法の総数を$f[i][y]$とするとき、$f[i][y] = \mathrm{dp}_i[N-1][y]$であるから、

$$f[i][y] = \mathrm{dp}[N][y] - \mathrm{dp}[N][y-1] + f[i][y-a_i-1]$$

となり、$f$についてDPすればクエリに${O}(1)$で答えられることになる。${O}(NM + Q)$。

---

戻すDPというらしい。

参考:
http://sigma425.hatenablog.com/entry/2015/07/31/121439