Mujin Programming Challenge 2018:F - チーム分け
問題
https://atcoder.jp/contests/mujin-pc-2018/tasks/mujin_pc_2018_f
考え方
放送解説が秀逸。chokudaiさんが考察の進め方を解説している。
さて、まずは入力の数列をソートしても問題ないのでソートしておく。状態を定義するが、どのように状態を定義すればよいか難しい。
人ごとにグループの所属している状態を持つと、 程度の状態数になるのでそのようには考えない。誰がではなく、何人残っているか?であれば の状態数で考えることができる。残りの人数を状態として持つことを考える。
グループの人数を決め打つとどこからどこまでが対象なのか明確になる。人数の決め打ちは制約の厳しい状態から考えていく。人数が多い場合のほうが厳しく、グループになりうる人が上から決まっていく。よってDPの遷移を決めることができる。
人以上のグループまで作っていて、 人以上のグループを許容する人が 人残っているときの場合の数
と定義する。 人のグループを 個作るときすでに残っている 人に加えて、 人以上のグループになることができる人も新たにグループ分けの対象になる。それぞれ 人以上のグループになることができる人の数を として求めておこう。
DPの初期値は でDPの遷移は
となる。このDPの遷移の形は類題のGroupingに似ている気がする。
解は である。
Submission #4303359 - Mujin Programming Challenge 2018
どこに着目して考察するべきだったか
まずはソート。人ごとのグループ分けを考えるのではなく、人数で考えることがポイント。あとはグループ人数を決め打つことができるかどうか
何がバグっていたか
得た知見(典型ポイント)
- ソートしても問題ないときはソートしておく
- 何かを決め打つと状態が決まる(ある状態がどの状態に寄与するか)