天下一プログラマーコンテスト2014 予選B : E - カラオケランキング

本番ノータッチだったけど、部分点は狙えば良かったな…。
http://tenka1-2014-qualb.contest.atcoder.jp/tasks/tenka1_2014_qualB_e

問題

L種類の曲があるカラオケで、プレイヤーはそれぞれ採点機でK[i]点を取ることができる。

なお、今月プレイヤー以外にもこのカラオケで系N回曲を歌う人がいる。
他の人は、時系列にそってA[i]番目の歌をS[i]点で歌った。

今回カラオケに際し、プレイヤーが得られる得点は採点機の結果そのものではない。
採点機の結果をxとすると、x+(x-その月のそこまでのその曲の平均))点を得られる。(平均値の計算には、今回取ったx点も含む)

プレイヤーは、任意のタイミングで任意の歌を計M回歌うことができる。
総得点を最大化せよ。

解法

Greedyで最大得点を得られる曲をM回選べばよい。

各曲で得られる得点をpriority_queueに入れ、最大得点の曲を選択し、1回歌う。
1回歌うとその曲の平均値が変化し、その曲で得られる得点が変化するので、その値をまたpriority_queueに入れればよい。

問題は、各曲において最大得点が得られるタイミングの計算である。
他人が歌う曲がすべて同じA[i]=xと仮定する。
プレイヤーがy回目に歌うときに得られる得点は、他人がi曲歌ったS[i-1]の直後に歌うとK[x]+K[x]-(S[0]+S[1]+...+S[i-1]+y*K[x])/(i+y)となる。
yが増えるごとにこの値はK[x]に近づくが、iが大きいほどそのペースは鈍くなる。

ここでconvex hull trickの要領で「yが増えてくると、i番目の次は((i+1)や(i+2)番の人を飛ばして)j番目の次に歌うと良い」という順番を求めることができる。
あとはpriority_queueの処理に従い、ある曲を1回歌うごとにyが増えていくので、その曲で最大得点を得られるタイミングを再計算していけばよい。

convex hull trickの処理が合計O(N)、Priority_queueの処理がO(M*logL)かかる。

int L,N,M;
ll K[200010],num[200010],an[200010],ci[200010];
ll SS[200010];
vector<int> E[100010];
int pre[200010];

double score(int cur) {
	
	while(ci[cur]<E[cur].size()-1) {
		int o=E[cur][ci[cur]],n=E[cur][ci[cur]+1];
		if((SS[o]+K[cur]*an[cur])/(double)(num[o]+an[cur])<(SS[n]+K[cur]*an[cur])/(double)(num[n]+an[cur])) break;
		ci[cur]++;
	}
	int o=E[cur][ci[cur]];
	return (SS[o]+K[cur]*an[cur])/(double)(num[o]+an[cur]);
}

void solve() {
	int f,i,j,k,l,x,y;
	double dd;
	
	cin>>L>>N>>M;
	FOR(i,L) cin>>dd, K[i]=dd*1000+0.1;
	FOR(i,L) E[i].push_back(100000+i), pre[i]=100000+i;
	FOR(i,N) {
		cin>>x>>dd;
		x--;
		SS[i]=SS[pre[x]]+dd*1000+0.1;
		num[i]=1+num[pre[x]];
		while(E[x].size()>=2) {
			j=E[x][E[x].size()-1];
			k=E[x][E[x].size()-2];
			if((SS[i]-SS[k])*(num[j]-num[k])>(SS[j]-SS[k])*(num[i]-num[k])) break;
			E[x].pop_back();
		}
		E[x].push_back(i);
		pre[x]=i;
	}
	
	priority_queue<pair<double,int> > Q;
	vector<pair<int,int> > R;
	FOR(i,L) an[i]++, Q.push(make_pair(K[i]+K[i]-score(i),i));
	while(M--) {
		int cur=Q.top().second;
		Q.pop();
		if(E[cur][ci[cur]]>=100000) R.push_back(make_pair(0,cur+1));
		else R.push_back(make_pair(E[cur][ci[cur]]+1,cur+1));
		an[cur]++;
		Q.push(make_pair(K[cur]+K[cur]-score(cur),cur));
	}
	
	sort(R.begin(),R.end());
	FOR(i,R.size()) _P("%d %d\n",R[i].first,R[i].second);
	
}

まとめ

これはぱっと見convex hull trickだ…とまでは気づけたけど、うまく適用するのに手こずった。