Mujin Programming Challenge 2018:F - チーム分け

問題

https://atcoder.jp/contests/mujin-pc-2018/tasks/mujin_pc_2018_f

考え方

放送解説が秀逸。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] である。

Submission #4303359 - Mujin Programming Challenge 2018

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

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

何がバグっていたか

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

  • ソートしても問題ないときはソートしておく
  • 何かを決め打つと状態が決まる(ある状態がどの状態に寄与するか)

類題