CODEFESTIVAL2018 Final G:Chicks and Cages

う

問題

解法

　dpっぽい雰囲気はあるが、何の整理もなしにはうまくいかない。まず、ある鳥かごに振り分けられたひよこの集合を $X$ とする。この鳥かごで発生するストレスの値は $|X|\sum_{i \in X} A_i$ である。つまりストレスの値の総和は、ひよこの大きさに、そのひよこが入っている鳥かごのひよこの数を係数としてかけた値の総和ということになる。これがわかると、小さいひよこにできるだけ大きい係数を、大きいひよこにはできるだけ小さい係数をかけたくなる。実際、2つのある鳥かごに振り分けられたひよこの集合を $X,Y$ とし、 $|X| \lt |Y|$ とする。このとき、 $i\in X,j\in Y$ かつ $A_i \gt A_j$ がなりたつ $(i,j)$ の組があるとき、ひよこ $i$ とひよこ $j$ を入れかえることで、ストレスの総和を小さくできる。このことは、 $A_i$ の小さい順にひよこを鳥かごに振り分けることで得られる最適解が存在することを意味する。
　ここまでくると、 $A_i$ を昇順にsortして、 $dp_{i,j}$ : $i$ 番目のひよこを $j$ 個の鳥かごを用いて振り分けたときの最小値というdpができそうという気分になる。更新式は、 $A_i$ の累積和を $S_i$ として

$dp_{i,j} = \min(dp_{i-k,j-1}+k(S_i-S_{i-k})) (1\leq k \leq i)$

である。しかしこれでは $O(MN^2$ )となり間に合わない。この遷移を高速化できないだろうか？
　「大きいひよこにはできるだけ小さい係数をかけたい」という気持ちを思い出そう。この気持ちに立ち返ると、 $i$ が大きくなるにしたがって、調べるべき $k$ は小さくなっていくのではないか？という予想が立つ。実際、sortした後であれば、 $j$ 番目の鳥かごのに入ってるひよこの数を $k_j$ とすると、最適解においては $k_j \geq k_{j+1}$ が成り立たなければならない。これを勘案すると、 $dp_{i,j}$ を更新する際には、 $k$ の値として $i/j$ まで考えれば十分であることがわかる( $k_1=k_2=\cdots=k_j$ みたいな状況が $k_j$ が最大となるときに考えられる振り分け方だから)。従って更新式は