差分

このページの2つのバージョン間の差分を表示します。

--- programming_algorithm:contest_history:atcoder:2019:0106_educational_dp [2019/01/10] – [解法] ikatakos
+++ programming_algorithm:contest_history:atcoder:2019:0106_educational_dp [2019/01/11] – [解法] ikatakos
@@ 行 1: / 行 1: @@
-======Educational DP Contest I,K,Lメモ======
+======Educational DP Contest I,K,L,Mメモ======
 [[https://atcoder.jp/contests/dp|Educational DP Contest / DP まとめコンテスト - AtCoder]]
@@ 行 168: / 行 168: @@
 print(dp[0][n])
 </sxh>
+===== M - Candies =====
+[[https://atcoder.jp/contests/dp/tasks/dp_m|M - Candies]]
+==== 問題 ====
+  *  $K$  個のキャンディを、余りなく  $N$  人の子供に分ける
+  * 各子供には上限  $a_1,a_2,...,a_N$  が決められており、 $i$  人目の子供には 0以上 $a_i$ 以下の個数のキャンディをあげることができる
+  * 配り方のパターン数を、 $\mod{10^9+7}$  で求めよ
+  *  $1 \le N \le 100$
+  *  $1 \le K \le 10^5$
+==== 解法 ====
+愚直にやる方法は基本的なDPで実装できるけど、遷移が多くてTLEになるので、上手く圧縮する。
+===愚直な方法===
+==データ==
+ $DP[i][j]=i$ 人目までの子供に、合計  $j$  個の飴を配るパターン数
+として考える。 $j$  の範囲は  $0～K$  で用意することになる。
+==初期状態==
+ $DP[0][0]=1$ 、後は0
+==遷移==
+ $i-1$  までのDPが以下のような感じで、 $a_i=2$  だった場合の遷移を考える。
+  ↑j |   ...                 ...
+|   25     25 +20 +15 = 60
+|   20     20 +15 + 9 = 44
+|   15     15 + 9 + 8 = 32
+|    9      9 + 8 + 1 = 18
+|    8      8 + 1     =  9
+|    1      1         =  1
+  ----+-------------------------
+      |   i-1                  i
+                         ↑2個配った時の遷移
+                     ↑1個配ったときの遷移
+                 ↑0個配ったときの遷移
+この、○個配ったときの各遷移の各  $j$  につき、 $DP[i-1]$  の参照と  $DP[i]$  への加算が発生するので、 $i-1$  から  $i$  への遷移で計算が  $K \times a_i$  回発生することになる。それぞれ上限  $10^5$  なので、間に合わない。
+  擬似コード
+  for i in 1..N:
+      for k in 0..a:
+          for j in 0..K:
+              dp[i][j+k] += dp[i-1][j]
+===圧縮===
+==遷移==
+全体を把握するため、もう少し少ない例でやってみる。
+  ↑j |                               1=1
+|                             1+2=3
+|                           1+2+2=5
+|                   1=1   1+2+2+1=6
+|                 1+1=2   2+2+1  =5
+|         1=1   1+1  =2   2+1    =3
+|   1   1  =1   1    =1   1      =1
+  ----+-----+-------+---------+-----------
+      |   0    a1=1      a2=2        a3=3
+/*
+なんか規則性がありそう。
+「 $a_i$  による上限を設けない」場合との差を考えてみる。
+  ↑j |            ...
+|              1+2+2+1=6       1+2+2+1=6
+|            1+2+2+1  =6       2+2+1  =5
+|          1+2+2+1    =6       2+1    =3
+|        1+2+2+1      =6       1      =1
+|  1   1+2+2+1        =6
+|  2   2+2+1          =5
+|  2   2+1            =3
+|  1   1              =1
+  ----+----+-------------------+--------------------
+      | i=2               i=3    i=3における上限あるなしの差分
+上限を設けない場合、配り方のパターン数は、直前の状態(1,2,2,1)の累積和となる。また、差分は、累積和をそのまま  $a_i+1$  だけずらしたものとなる。
+よって、累積和でまとめてしまえば、1回の遷移にかかる計算を上限  $K$  回に省略でき、間に合う。
+*/
+ $a_3$  に着目すると、
+  *  $j=0～3$  に  $DP[2][0]=1$  を加算
+  *  $j=1～4$  に  $DP[2][1]=2$  を加算
+  *  $j=2～5$  に  $DP[2][2]=2$  を加算
+  *  $j=3～6$  に  $DP[2][3]=1$  を加算
+という区間加算で表される。よって、いもす法による累積和で高速化できる。
+  *  $DP[3][0]$ に1、 $DP[3][4]$ に-1を加算
+  *  $DP[3][1]$ に2、 $DP[3][5]$ に-2を加算
+  *  $DP[3][2]$ に2、 $DP[3][6]$ に-2を加算
+  *  $DP[3][3]$ に1、 $DP[3][7]$ に-1を加算
+  *  $DP[3]$ の累積和を取る
+ここで、正の加算の部分はそのまま $DP[2]$ で流用でき、負の部分は $DP[2]$ を $a_i+1$ だけずらして正負逆転させたものに一致する。
+よって、計算量を上限 $K$ 回の減算+累積和の計算に省略でき、間に合う。
+<sxh python>
+from itertools import accumulate, starmap
+from operator import sub
+n, k = map(int, input().split())
+aaa = list(map(int, input().split()))
+MOD = 10 ** 9 + 7
+dp = [0] * (k + 1)
+dp[0] = 1
+for a in aaa:
+    dp = list(accumulate(dp))
+    dp[a + 1:] = starmap(sub, zip(dp[a + 1:], dp[:-a - 1]))
+    dp = [x % MOD for x in dp]
+print(dp[k])
+</sxh>
+このような行列同士の四則演算はNumPyを使いたくなるけど、一括で累積和を計算したらオーバーフローを起こすのか、WAになってしまった。
+う～ん、 $K$ の上限が $10^6$ で、各項が剰余を取って $10^9+7$ 未満なので、最大でも $10^{15}$ 強にしかならないはずなんだけどなあ。WAの原因は他にあるのだろうか。