AtCoder Regular Contest 067:E - Grouping

問題

https://atcoder.jp/contests/arc067/tasks/arc067_c

考え方

漸化式的な考え方でDPをする。難しい。

dp[i][j] := i 人未満のグループのみで j 人を分ける場合の数

と定義する。dp[i][j] を用いると N 人のうち j 人はすでにグループが決まっているため残りの N-j 人のグループ分けについて考えれば良い。

そのとき

  • \displaystyle dp[i+1][j+i] += dp[i][j] * {}_{N-j} \mathrm{C}_i
  • \displaystyle dp[i+1][j+2*i] += dp[i][j] * {}_{N-j} \mathrm{C}_i * {}_{N-j-i} \mathrm{C}_i * \frac{1}{2!}
  • \cdots

であるから一般的に書くと

  • \displaystyle dp[i+1][j+k*i] += dp[i][j] * {}_{N-j} \mathrm{C}_i * {}_{N-j-i} \mathrm{C}_i \cdots * {}_{N-j-(k-1)i} \mathrm{C}_i * \frac{1}{k!}

である。

細かい注意点としては各グループ数 kC \le k \le D であることである。k \lt C なる k については場合の数に含めないが、コンビネーションの累積積の計算は必要。

Submission #4234421 - AtCoder Regular Contest 067

どこに着目して考察するべきだったか

N 人のグループ分けの場合の数を求めたいので、DPとして今分けようとしている人数を状態に持つことは自然な気がする。加えてちょうと i 人でのグループ分けは組み合わせで求めることができるのですでに i-1 人でのグループ分けが完了している、という状態を持つのも自然な気もする。

何がバグっていたか

得た知見(典型ポイント)

  • 漸化式的なDP...(ポイントが難しい)

類題