Hatena::Grouptopcoder

Hiro180の日記

 | 

2016-06-12最近解いた問題

SRM691 Div1 Med 23:48

<問題概要>

仕事がN個あり、経験値と係数が決められている。得られる収入は(これまでの経験値の総和)*(その仕事の係数)である。

ただし、Nは偶数で、N/2個仕事をした時点で研修に参加し経験値がX増えるものとする。

収入を最大化せよ。 (N<=50,経験値,X<=100000,係数<=10)

<解法>

X=0の場合を考える。

(経験値、係数) = (ex1,co1),(ex2,co2)の2つの仕事を考える。これまでの経験値をexpとすると、収入は

・前者->後者: (exp+ex1)*co1 + (exp+ex1+ex2)*co2

・後者->前者: (exp+ex2)*co2 + (exp+ex1+ex2)*co1

となるので、(前後はどちらも同じ。)

実質ex1*co2とex2*co1の比較であり、それはつまりex1/co1 と ex2/co2の比較である。

以上より、(exp/coef)が大きい方からやるのが良いと分かった。 (こういう問題、150問に1問くらいのペースで見るイメージがある)

X>0の時にはこれではうまくいかない。しかし、Xの前後ではそれぞれこの順番で並べるのが良いので、

順に振り分けていくDPを考える。

ここで、収入の計算方法を

(exp1+exp2+.....+expE) * coEを毎回加えるのではなく、(coE+co(E+1)....+coN) * expEを毎回加えるという発想をすると、

研修の前にやった仕事に対する係数の総和を決め打ちすると(tmpCoとする)

前に振り分けたときは(sum(co)-sum(振り分け済みの前のco)) * exp

後ろに振り分けたときは(sum(co)-tmpCo-sum(振り分け済みの後ろのco)) * exp

を毎回加えればOK。

計算量は50 * 25 * 250のDPを25*10回くらいするのでまぁ通る。 良問。

 |