ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

Educational DP Contest / DP まとめコンテスト M - Candies

問題
提出コード

解法

普通にDPを考えてみます。
dp[i][j] = i人目までにキャンディを配り終え、j個のキャンディが残っている状態になるような場合の数
とすると、dp[N][0]が答えとなります。
さて、i人目にキャンディを配るとき、0a_{i}個の中で好きな個数を選ぶことができます。つまり、i人目までに配り終えた段階で残りキャンディがj個となるには、i-1人目まで配り終えた段階ではjj+a_{i}個残っている可能性があります。
ということで、DPの遷移は次のようになります。
\displaystyle dp[i][j] = \sum_{m=0}^{a_{i}} dp[i-1][j+m]
ただし、j+mK以下という条件も存在することに気を付けてください。
これで、一応DPを組むことはできました。が、このままだと総和の部分でもループが必要になり、時間内に解くことができません。そこで、
\displaystyle sum[i][j] = \sum_{p=0}^{j} dp[i][p]
とすると、次のような2つの式を立てることができます。
\displaystyle sum[i][j] = sum[i][j-1] + dp[i][j]
これは累積和と同じ考えです。
dp[i][j] = sum[i-1][min(j+a_{i},K)] - sum[i-1][j-1]
これは、DPのjmin(j+a_{i},K)の総和の部分を、累積和を利用して抽出する式で置き換えたものになります。
あとは、下の式を上の式に代入すると、最終的に次のような遷移ができあがります。
sum[i][j] = sum[i][j-1] + sum[i-1][min(j+a_{i},K)] - sum[i-1][j-1]
そして、dp[N][0] = sum[N][0]であるので、結局はsumについてのみ遷移を利用して計算を行い、sum[N][0]をチェックすれば、答えを求めることができます。

感想

実は、この問題は以下の記事の問題と本質的にはまったく同じです。

emtubasa.hateblo.jp

今回は、1から自分で考えたので、上の記事の遷移とは違うものになっています(上の記事は、蟻本をもとに作成しています)。
昔は自分では何もできなかった問題が、このように自力で解けるようになっているので成長したな、と思います。
ただ、この問題を読んだときにパッとは解法が思い浮かばなかったので、その点ではまだまだ精進が必要だな、とも思いました(上の記事とまったく同じ、というのは解き終わってから気づいたので、その点でも記憶力があまりないかなぁと)。
思考の流れとしては、今回はDPという大ヒントが与えられているのでDPを考えるのですが、それぞれの人に対するキャンディの個数を情報として持つのがもちろん無理なので、合計値を持っておくしかない、ということになりました。すると、何人目まで上げたか、という情報と残りいくつか、という情報をもとに遷移していくしかないなぁ、ということになり、dp[i][j]の式ができました。で、このままだと解けないので、累積和がうまく使えそうだから式変形してみよう、ということで式変形をするとうまくいきました。最後の式変形でほぼ躓かなかったのは良かったと思います。