EDPC M - Candies

飴

考え方

ABCでいうと、E問題級。

一見、子供を $1$ 人ずつ増やしながら、飴の個数ごとの配り方を継承するだけの動的計画法。

しかし、マスの数が最大で $100 \times 10^5 = 10^7$ 個ある。
そして、$1$ つのマスを埋めるのに最大 $10^5$ 個の数を足し算しないといけない。
つまり、愚直にやると TLE する。

ということで、最大 $10^5$ 個の数を足し算しなくて済むように、sliding window 法を使う。
以上……ではあるのだが、$2$ つのアルゴリズムのコードが絡まる都合で、実装がとてもややこしい。

計算量は $O(NK)$。

入力を受け取る。

n: 3
k: 4
a: {1, 2, 3}

dp[i] を、ここまで見た子供たちに合計 i 個の飴を配る方法数とする。

最初は、誰にも配っていないので、飴 $0$ 個を配る方法が $1$ 通りである。

dp: {1, 0, 0, 0, 0}

$1$ 人目の子供には、飴を $0$ 個以上 $1$ 個以下渡せる。
（ほとんど $0$ で意味のある更新の様子がよく見られないので省略）

dp: {1, 1, 0, 0, 0}

$2$ 人目の子供には、飴を $0$ 個以上 $2$ 個以下渡せる。
（ほとんど $0$ で意味のある更新の様子がよく見られないので省略）

dp: {1, 2, 2, 1, 0}

$3$ 人目の子供には、飴を $0$ 個以上 $3$ 個以下渡せる。
更新前の DP テーブルは次の状態である。

dp: {1, 2, 2, 1, 0}

dp[i] 自身はそのまま残し、sum に dp[i-3] から dp[i-1] までの和を持たせて足す。
そして、$i$ を $1$ つ減らすたびに、その区間を $1$ つ左へずらす。

まず、$i=4$ のときは、sum に次の和を持たせている。

sum = dp[1] + dp[2] + dp[3]
    = 2 + 2 + 1
    = 5

したがって、dp[4] は次のように更新される。

dp[4] = 0 + 5
      = 5

次に、$i=3$ の計算へ移るため、窓を $1$ つ左へずらす。
今まで窓に入っていた dp[3] を取り除き、新しく dp[0] を加える。

sum = 5 - dp[3] + dp[0]
    = 5 - 1 + 1
    = 5

この sum は、dp[0] + dp[1] + dp[2] に対応する。
よって、dp[3] は次のように更新される。

dp[3] = 1 + 5
      = 6

同じように窓を左へずらしながら処理すると、次のようになる。

i=2: sum = 3, dp[2] = 2 + 3 = 5
i=1: sum = 1, dp[1] = 2 + 1 = 3
i=0: sum = 0, dp[0] = 1 + 0 = 1

ここで参照している dp の値は更新前のものである。
右から左へ処理しているので、必要な値はまだ上書きされていない。

実際に全体を更新すると、次のようになる。

dp: {1, 3, 5, 6, 5}

dp[4] の $5$ が答え。

答えは $10^9+7$ で割った余りを要求されているので、剰余類環の考えに従って処理する。
足し算や引き算をするたびに結果を % 1000000007 する。
引き算で負になることがあるので、出力前に負数を補正する。

特になし。