読者です 読者をやめる 読者になる 読者になる

tokoharuの落書き帳

らくがきですよ

D問題(速報)

・なにこれ ->
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)でできる