AtCoder Regular Contest 067:E - Grouping
問題
https://atcoder.jp/contests/arc067/tasks/arc067_c
考え方
漸化式的な考え方でDPをする。難しい。
人未満のグループのみで 人を分ける場合の数
と定義する。 を用いると 人のうち 人はすでにグループが決まっているため残りの 人のグループ分けについて考えれば良い。
そのとき
であるから一般的に書くと
である。
細かい注意点としては各グループ数 は であることである。 なる については場合の数に含めないが、コンビネーションの累積積の計算は必要。
Submission #4234421 - AtCoder Regular Contest 067
どこに着目して考察するべきだったか
人のグループ分けの場合の数を求めたいので、DPとして今分けようとしている人数を状態に持つことは自然な気がする。加えてちょうと 人でのグループ分けは組み合わせで求めることができるのですでに 人でのグループ分けが完了している、という状態を持つのも自然な気もする。
何がバグっていたか
得た知見(典型ポイント)
- 漸化式的なDP...(ポイントが難しい)