Mujin Programming Challenge 2018 F - チーム分け(600)
解法
良解説を聞くのが良い
- とりあえずsortして分布(c[x] := #( a_i=x なる i ) )をまとめておく
- 1人ずつグループに入れていこうとすると,分布(k人グループが何個できているか)を持たないといけないので状態が指数時間になって無理
- 視点を変えて,人数がk人であるようなグループを全て作っていく,というようなことを考える
- 昇順にやっていこうとすると,2人組を作るときにaの値が(2,3)をペアにするのと(2,4)をペアにするのは区別しないといけない
- 降順を考えると,x人のグループを作ろうとしているときにa_i>=xであるようなa_iは区別しなくていいことに気づけたら勝ち
def.
dp[i][j] := (i人以上のチームをすでに作っていて, i人チームを作るときに自由に使える人がj人残っている)
初期.
dp[N+1][0] = 1
遷移.
解説の通り
ans.
dp[1][0]
メモ
これむずいけど好き.
制約はゆるい方から決めて行った方がいいのかな
