CEOI2016 day2 - Popeala
解法
同じような dp を$ S回行う。一回の dp を$ O(TN)で行えば実行時間制限に間に合う。
$ \mathrm{dp}_iへの遷移を考える。$ j < iを徐々に大きくしていくと、問題$ j, \dots, i - 1を全て正解しているような生徒の人数は単調増加する。
遷移は$ \mathrm{dp}_i \leftarrow \min(\mathrm{dp}_i, \mathrm{dp}_j + n(\mathrm{sum}_i - \mathrm{sum}_j))のような形になっており、$ nに対する$ \mathrm{dp}_j - n \times \mathrm{sum}_jの最小値を記録しておけば良い。
問題$ j, ..., i - 1を全て正解している生徒が$ n人以下であるような$ jの最大値を$ \mathrm{pos}_{i, n}とおく。これは$ O(TN\log N)で前計算できる。
$ \mathrm{pos}_{i, n}が$ iについて単調増加であることから、$ j \leq \mathrm{pos}_{i, n}における$ \mathrm{dp}_j - n \times \mathrm{sum}_jの最小値を記録することは全体で$ O(T)でできる。
ここで、正解者数が$ n未満となるような$ jに対して$ \mathrm{dp}_j - n \times \mathrm{sum}_jが記録されてしまう可能性があるが、そのような$ jについては、さらに$ nが小さい場合にも計算されているはずであり、$ \mathrm{dp}_j + n(\mathrm{sum}_i - \mathrm{sum}_j)は$ nについて単調増加であるので、これは無視して良い。
感想
単純だけど結構難しかった