Codeforces Round #598 (Div. 3) - E. Yet Another Division Into Teams
概要
N人いて、それぞれのprogramming skill(以降PSと略す)はa_iである。N人でいくつかチームを組む。3人以上の人間で１つのチームを組むことができる。
チームの不満度を、チーム内の最大のPSを持つ人と、最小のPSを持つ人との差と定める。
いくつかのチームがあったとき、それらの不満度は、個々のチームの不満度の和である。
どのようにチームを割り当てたら、全体の不満度を最小化できるか？
不満度の最小値と、その時のチームの割り当て方の1例を示せ。
制約： 3 <= N <= 2 * 10^5, 1 <= a[i] <= 10^9
ACするまで
1. パッと見、DPを感じる。
2. さて、どのようにチームを割り当てるのだろうか？チームは3人以上で組めるので、チーム人数もO(N)ありそう・・・
3. よく考えると、6人以上のチームを組む必要はない！
4. しかし、1hかけても実装できず・・・i cannnot solve in my virtual participation......
5. 実装を、がんばろう！
考察
チームの人数は、3人以上であれば何人でもよいので、O(N)人のチームまで考えられてしまう。
しかし、1つのチームを2チームに分割できれば、分割をした方が不満度は(同じか)下がる！という事実がある。
これが意味するのは、2チームに分割できるほどの人数を持つチーム、すなわち6人以上のチームは分割するべき、ということである。
ここで、同じPSの人を大量に同じチームに入れても、1人とみなせるので、同じPSを持つ人からなる6人以上のチームは、分割していない。(復元の便宜上)分割してもしなくても、不満度に対する寄与は同じだからである。もっと言えば、1つのチーム内にPSが異なる人が5人以下にする必要がある、ということである。
というわけで、チームの人数は実質的には5人までと考えることができる。a[i]をmapに入れて、小さい順に並べるとして次のようにDPテーブルを定める。
dp[i][j] := 1-idxで、i番目に低いPSを持つ人をチームに振り分け済みで、今のチームがj人になってるときの、最小の不満度。
遷移はどうなるのだろうか？
ひとまず、j == 0の時は、今のチームが0人、つまり新しくチームを始めるということである。この時、どのようなPSの人を入れても、不満度の増加はない。
逆に、それ以外の場合は、(小さい順に並んでる、)i-1番目のPSを持つ人は必ずチームに加わってることから、必ず不満度は、i-1番のPSとi番のPSの差だけ加算される。
というわけで、実装自体は、配るDP方式で書く。
遷移先はどうなるのかというと、次のような2パターンがある。今がj人として、i番目のPSを持つ人が、p人いるとする。(さきほど6人以上のチームを作らなくていいと言ったが、6人以上のチームを作っても不満度に差がない(同じPSを持つ人が大量にいるイメージ)ときは、復元の便宜上作っている。あくまで作らなくていいのは、PSが違う人同士からなる6人以上のチーム)
- (j + p) % 6人のチーム。 そのまま同じチームに突っ込む感じになる。
- (j + p) >= 3の時、[0, min(5, (j + p - 3))]人のチーム。 3人を超えたら、3, 4, 5人で1チームとして、残った0, 1, 2, 3, ...人で別のチームを作る、というのも可能である。
DPはこれを実装すればよい。
復元に関しては、DPのログをもっておき(ソースコード参考)、ログをたどって、不満度に変化がなかったら、チーム分けが行われている、として実装するとやりやすいと思う。
一言
分かっていたけど実装を詰め切れなかった。いつの日かまたやり直したい。
