Mail.Ru Cup 2018 Round 3 : F. Write The Contest

これもよくわからん問題。
http://codeforces.com/contest/1056/problem/F

問題

N個の問題が与えられる。
各問題は、難易度がA[i]、スコアがP[i]である。
問題は任意の順で解くことができる。

問題を解く時間は、難易度Aの他スキルレベルSで決まり、A/Sである。
また、問題を解く前には10分の空き時間を設けなければならない。

スキルは以下のように変化する。

• 初期値は1である。
• 1問目を解く前、スキルレベルを上昇する機会がある。t分間上昇させると、Ctだけスキルレベルが上昇する。
• 問題を解く前の10分の空き時間にスキルレベルは90%に低下する。

T分間の間に、解ききれる問題のスコアの最大値を求めよ。

解法

後に解くほどスキルレベルが低下するので、難易度が高い問題は先に解く方が良い。
よって解くかどうか検討する順番は難易度降順で一意に決まる。

ここで、NおよびスコアPが小さいことを考える。
DPの要領で以下を求めよう。
f(n,k) := スキルレベルが1のとき、n問解いて総スコアkを得るためにかかる時間

f(n,k)がわかったとき、スキルレベル上昇により全体をT分に押さえられるかを考える。
t分スキルレベル上昇を行う場合、かかる時間はである。これがT以下なら良い。
問題はtを何にするかであるが、この式の導関数が0になる点を考えると、の場合、とするのがよい。

int TC;
int N;
double T,C;
pair<int,int> P[101];

double dp[101][1001];
double po[102];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(i,102) po[i]=pow(1.0/0.9,i);
	
	
	cin>>TC;
	while(TC--) {
		cin>>N;
		cin>>C>>T;
		FOR(i,N) cin>>P[i].first>>P[i].second;
		sort(P,P+N);
		reverse(P,P+N);
		
		FOR(i,101) FOR(j,1001) dp[i][j]=1e12;
		dp[0][0]=0;
		
		FOR(i,N) {
			for(x=i;x>=0;x--) {
				for(y=10*x;y>=0;y--) if(dp[x][y]<1e12) {
					dp[x+1][y+P[i].second]=min(dp[x+1][y+P[i].second], dp[x][y]+P[i].first*po[x+1]);
				}
			}
		}
		
		int ma=0;
		FOR(x,N+1) FOR(y,x*10+1) if(y>ma) {
			double D=dp[x][y];
			
			
			double train=0;
			if(D*C>1) {
				train=(sqrt(D*C)-1)/C;
			}
			double S=1+train*C;
			if(D/S+train+10*x<=T) ma=y;
			
			
		}
		cout<<ma<<endl;
		
	}
}

まとめ

スキルレベル上昇はいつでもできると勘違いして、こんなん解けるかと思ってしまった。