今回も不参加です。
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); }
まとめ
結構苦戦した。