主食は米

主に競プロ備忘録

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]

メモ

これむずいけど好き.
制約はゆるい方から決めて行った方がいいのかな

コード