7K12 blog

猫でも分かるアルゴリズム解説

Educational DP Contest M - Candies

f:id:tkr987:20200318135601p:plain
https://atcoder.jp/contests/dp/submissions/10545854

 

f:id:tkr987:20200318145849p:plain

子供たちが飴を分け合うと言うと重複組み合わせっぽく見えるが、重複組み合わせだとDPが書きづらいので子供i-1から子供iに遷移するとき飴jがどうなるかというDPで実装する。このとき、K個の飴を配るというより逆転の発想で残りの飴がj個と考えて子供iが0からA[i]個の飴を取ると考えると実装が楽になる。

  • 初期値は rep(i, K-a[0], K) dp[0][i] = 1;
  • 繰り返しは rep(i, 1, N) rep(j, 0, K+1)
  • 状態は特に無し
  • 漸化式は dp[i][j] = dp[i-1][j] + dp[i-1][j+1] + dp[i-1][j+2] + ... + dp[i-1][j+A[i]];
  • 最終目標は dp[N][0]

 

vector<DS_BinaryIndexedTree<mll>> bitdp(N + 1, DS_BinaryIndexedTree<mll>(K + 1));

点加算と区間取得が出来れば良い。自作の遅延セグ木では定数倍が大きすぎてTLEしてしまったので、BIT(Binary Indexed Tree)を使った。[j]の部分をBIT1本で表現し、BITを最大100本用意すれば解くことが出来る。

  • 重複組み合わせでなく、遷移を意識する
  • 逆転の発想で残りの飴がj個
  • 子供iが0からA[i]個の飴を取る遷移(矢印)を意識する
  • 最終目標を想像する、子供Nが残りの飴0、dp[N][0]
  • dp[i][0からK]の0からKは1本のBITで表現できる