Codeforces #488 Div1 D. Compute Power

問題設定に無理があるような。
http://codeforces.com/contest/993/problem/D

問題

N個のタスクがある。
各タスクiは消費電力をA[i]食い、プロセッサをB[i]個消費する。

ここに無限個コンピュータがある。
それぞれ無限個のプロセッサが存在するが、１個のコンピュータでは同時に処理できるタスクは１個である。
各コンピュータは最大２個まで連続でタスクを処理できる。
全コンピュータ１個目の割り当てタスクを同時に行い、その後同時に２個目を開始する。
また、２個目のタスクは１個目より消費電力が低くなければならない。

最適なタスク割り当てをした場合、１個目のタスク実行時にプロセッサ当たりの平均消費電力を最小化せよ。

解法

2分探索で解く。
平均値の仮の値をvとしたとき、各タスクの消費電力を(A[i]-B[i]*v)と考え、その総和が０以下になるような割りあてを考えればよい。

割り当てはA[i]を降順に行おう。
状態として以下の３値を取ると、毎回の判定をO(N^3)のDPで実行できる。

• ２個タスク割り当て済みのコンピュータ数
• １個タスク割り当て済みのコンピュータ数
  • 直前に割り当てたタスクが次割り当て予定のものと消費電力が等しいものの数
  • 直前に割り当てたタスクが次割り当て予定のものより消費電力が大きいものの数

int N;
pair<int,int> P[51];
double dp[52][52][52];

int ok(double a) {
	int i;
	vector<double> V;
	FOR(i,N) V.push_back(P[i].first-P[i].second*a);
	
	int x,y,z;
	FOR(x,52) FOR(y,52) FOR(z,52) dp[x][y][z]=1e9;
	dp[0][0][0]=0;
	double mi=1e9;
	FOR(i,N) {
		FOR(x,52) FOR(y,52) {
			int z=i-2*x-y;
			if(z<0) break;
			if(y) dp[x+1][y-1][z]=min(dp[x+1][y-1][z],dp[x][y][z]);
			dp[x][y][z+1]=min(dp[x][y][z+1],dp[x][y][z]+V[i]);
		}
		if(i<N-1 && P[i].first!=P[i+1].first) {
			FOR(x,52) FOR(y,52) {
				int z=i-2*x-y+1;
				if(z>0) dp[x][y+z][0]=min(dp[x][y+z][0],dp[x][y][z]);
			}
		}
	}
	FOR(x,52) FOR(y,52) FOR(z,52) if(2*x+y+z==N) mi=min(mi,dp[x][y][z]);
	
	return mi<=0;
	
}



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>P[i].first;
	FOR(i,N) cin>>P[i].second;
	sort(P,P+N);
	reverse(P,P+N);
	
	double L=0,R=1e9;
	FOR(i,60) {
		double M=(L+R)/2;
		if(ok(M)) R=M;
		else L=M;
	}
	cout<<(ll)(1000*L+0.99)<<endl;
	
}

まとめ

今回全体的に問題文が難しすぎ。