kmjp's blog

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

Google Code Jam 2018 Round1B : A. Rounding Error

今回も不参加です。
https://codejam.withgoogle.com/2018/challenges/0000000000007764/dashboard

問題

N人で好きなプログラミング言語に投票を行う。

現在投票を途中まで行ったところ、L個の言語に票が入っている。
最後まで票が入ったら、各言語が占める得票率のパーセンテージを求める。
このパーセンテージでは小数第1位で四捨五入し、整数化される。

残りの投票後における、整数化後のパーセンテージの総和の最大値を求めよ。

解法

N≦100の場合、DPでi番目までの言語の総票数と整数化後のパーセンテージの総和の最大値を求めよう。
N>100の場合、1票入ってもパーセンテージが増えるかどうかわからない。

そこで、次にパーセンテージが増えるまで必要な得票数の少ない順に投票させよう。
これはpriority_queueで実現できる。

int N,L,ON;
int C[101010];
int num[101010];
int pat[102];

int nex(int cur) {
	int n=num[cur]+1;
	while(pat[n]>=1<<20 && n<100) n++;
	return pat[n];
}

int dp[251][251];

void solve(int TC) {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>L;
	ON=N;
	FOR(i,101) pat[i]=1<<20;
	for(i=0;i<=N;i++) {
		x = (int)(i*100.0/N+0.5+1e-9);
		num[i]=x;
		pat[x]=min(pat[x],i);
	}
	num[N+1]=pat[101]=1<<30;
	
	int ret=0;
	set<pair<int,int>> M;
	
	if(N>250) {
		FOR(i,ON) {
			if(i<L) cin>>C[i];
			else C[i]=0;
			N-=C[i];
			ret+=num[C[i]];
			M.insert({nex(C[i])-C[i],i});
		}
		
		while(N>0) {
			auto a=*M.begin();
			M.erase(M.begin());
			if(N<a.first) break;
			N-=a.first;
			x=a.second;
			ret+=num[nex(C[x])]-num[C[x]];
			C[x]=nex(C[x]);
			M.insert({nex(C[x])-C[x],i});
		}
	}
	else {
		FOR(i,ON) {
			if(i<L) cin>>C[i];
			else C[i]=0;
		}
		
		ZERO(dp);
		FOR(i,ON+1) FOR(j,ON+1) dp[i][j]=-1<<30;
		dp[0][0]=0;
		FOR(i,ON) {
			for(j=C[i];j<=ON;j++) for(k=0;k+j<=ON;k++) {
				dp[i+1][j+k]=max(dp[i+1][j+k],dp[i][k]+num[j]);
			}
		}
		
		ret=dp[ON][ON];
		
	}
	
	_P("Case #%d: %d\n",TC, ret);
}

まとめ

結構苦戦した。