D問題(速報) - tokoharuの落書き帳

・なにこれ ->
D: 夕食 - Japan Alumni Group Summer Camp 2014 Day 4 | AtCoder

・解法の一例

自炊定数を $P$ として初期自炊力（自炊のうまさ）をQとしておく。
日数は0-indexedとしておく。
$j$ 日目の食堂幸福度を $C_j$ としておく。
さて、 $K$ 個食堂から選ぶこととする。
このとき自炊幸福度を(足す分だけ)考えると $(N-K)*(N-K-1)/2 + Q(N-K)$ とできる。
$a_i$ 日目( $0 \leq i \leq K-1$ )に食堂にいったとして
$a_i$ 日目の幸福度は,
先ほどの自炊幸福度で差し引かなかった食堂に行ったことから来る幸福度の損失を含めて考えることで、
$a_i$ 日目の時にできる幸福度は $(N-K-(a_i-i))*(-1)*P + C_{a_i}$ と解釈できる。
(それまでに $a_i-i$ 回自炊をした。つまり、これ以降で自炊は $N-K-(a_i-i)$ 回行うので,先程足した分から引く必要がある。

この評価で計算してみると
$PQ(N-K) + P\frac{(N-K)(N-K-1)}{2} + \sum_{i=0}^{K-1} -P(N-K-a_i+i)+C_{a_i}$

Sumの外に出せるものを出すと
$PQ(N-K) + P\frac{(N-K)(N-K-1)}{2} - P\frac{K(K-1)}{2} -PK(N-K) + \sum_{i=0}^{K-1} P a_i +C_{a_i}$

$= PQ(N-K) + P(N-K)(N-K-1) - P\frac{N(N-1)}{2} + \sum_{i=0}^{K-1} P a_i + C_{a_i}$

(最後の変形は別解から考えると出てくる式なのでイコールで結んでおいた。以後の議論では必要ない変形)となる。
足し算の中身が $a_i$ のみに依存している形になるので、これの最大値は
$b_i = Pi + C_i$ を定義してこれの大きい方から $K$ 個選択すれば良い。
しかも $K$ にも依存しないので $b_i$ を始めに定義しておいて、 $K$ の値を0から順番に試していき最大値を出せば良い。　
したがってネックはソートのみ。時間計算量 $O(N log N)$ でできる