Codeforces #412 Div1 B. Dynamic Problem Scoring

面倒な問題。
http://codeforces.com/contest/806/problem/B

問題

CodeforcesのDynamic Scoring方式で５問の問題からなるスコアを考える。
参加者中正答者の割合で問題のスコアが決まる。

• 1/32以下 : 3000
• 1/32超1/16以下 : 2500
• 1/16超1/8以下 : 2000
• 1/8超1/4以下 : 1500
• 1/4超1/2以下 : 1000
• 1/2超 : 500

また、コンテスト開始後1分ごとに得られるスコアが1/250だけ減少する。

さて、N人の参加者のコンテストにおける回答状況が与えられる。
1番の参加者は、2番の参加者に何とかして勝ちたい。
そのため、任意の人数の参加者を追加し、Dynamic Scoringを操作できる。
追加の参加者は、1番の参加者が解いた問題に関しては解いても解かなくてもよい。1番の参加者が解けない問題は解けない。

1番の参加者が2番の参加者に勝つためには、最小何人追加すればよいか。

解法

A問題と似ているが、まず何人追加した場合に、各問題でどのスコアにすることができるかを事前に総当たりしよう。
最小で1/32がスコアの境界なので、N*32程度の人数までやっておけばよい。

あとは、各問題がどのスコアになるかを6^5通り総当たりし、1番の参加者が勝利可能なもののうち、最少人数で達成可能なものを選ぼう。

int N;
int P[200][5];
int num[5];
int D[5];
int p6[10];
int can[5005][6][7];

int cat(int p,int q) {
	if(p*32<=q) return 5;
	if(p*16<=q) return 4;
	if(p*8<=q) return 3;
	if(p*4<=q) return 2;
	if(p*2<=q) return 1;
	return 0;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		FOR(x,5) {
			cin>>P[i][x];
			if(P[i][x]>=0) {
				P[i][x]=500-2*P[i][x];
				num[x]++;
			}
		}
	}
	
	for(i=N;i<=5000;i++) {
		FOR(x,5) {
			if(P[0][x]>=0) {
				FOR(y,i-N+1) can[i][x][cat(num[x]+y,i)]=1;
			}
			else {
				can[i][x][cat(num[x],i)]=1;
			}
		}
	}
	
	
	p6[0]=1;
	FOR(i,6) p6[i+1]=p6[i]*6;
	
	int ret=1<<30;
	FOR(i,p6[5]) {
		int A=0,B=0;
		FOR(x,5) {
			D[x]=i/p6[x]%6;
			if(P[0][x]>=0) A+=(D[x]+1)*P[0][x];
			if(P[1][x]>=0) B+=(D[x]+1)*P[1][x];
		}
		if(A<=B) continue;
		
		for(y=N;y<=5000;y++) {
			int ok=1;
			FOR(x,5) ok &= can[y][x][D[x]];
			if(ok) break;
		}
		
		if(y<=5000) ret=min(ret,y-N);
		
	}
	
	if(ret==1<<30) ret=-1;
	cout<<ret<<endl;
	
}

まとめ

色々解法があるが、どれも面倒。