kmjp's blog

競技プログラミング参加記です

Codeforces #488 Div1 D. Compute Power

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

問題

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

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

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

解法

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

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

  • 2個タスク割り当て済みのコンピュータ数
  • 1個タスク割り当て済みのコンピュータ数
    • 直前に割り当てたタスクが次割り当て予定のものと消費電力が等しいものの数
    • 直前に割り当てたタスクが次割り当て予定のものより消費電力が大きいものの数
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;
	
}

まとめ

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