問題

考え方

放送解説が秀逸。chokudaiさんが考察の進め方を解説している。

さて、まずは入力の数列をソートしても問題ないのでソートしておく。状態を定義するが、どのように状態を定義すればよいか難しい。

人ごとにグループの所属している状態を持つと、 $O(2^n)$ 程度の状態数になるのでそのようには考えない。誰がではなく、何人残っているか？であれば $O(N)$ の状態数で考えることができる。残りの人数を状態として持つことを考える。

グループの人数を決め打つとどこからどこまでが対象なのか明確になる。人数の決め打ちは制約の厳しい状態から考えていく。人数が多い場合のほうが厳しく、グループになりうる人が上から決まっていく。よってDPの遷移を決めることができる。

$dp[i][j] := i$ 人以上のグループまで作っていて、 $i$ 人以上のグループを許容する人が $j$ 人残っているときの場合の数

と定義する。 $i-1$ 人のグループを $k$ 個作るときすでに残っている $j$ 人に加えて、 $i-1$ 人以上のグループになることができる人も新たにグループ分けの対象になる。それぞれ $i$ 人以上のグループになることができる人の数を $cnt[i]$ として求めておこう。

DPの初期値は $dp[n+1][0] = 1$ でDPの遷移は

$\displaystyle dp[i-1][j + cnt[i-1] - (i-1) * k] += dp[i][j] * \prod_{i=1} {}_{j + cnt[i-1] - (i-1) * k} \mathrm{C}_{i-1} * \frac{1}{k!}$

となる。このDPの遷移の形は類題のGroupingに似ている気がする。

解は $dp[1][0]$ である。

まずはソート。人ごとのグループ分けを考えるのではなく、人数で考えることがポイント。あとはグループ人数を決め打つことができるかどうか