読者です 読者をやめる 読者になる 読者になる

kmjp's blog

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

Google Code Jam 2015 Qualification Round : A. Standing Ovation

GCJ

今年もGCJに参加。無事100ptでした。
https://code.google.com/codejam/contest/6224486/dashboard#s=p0

問題

オペラの聴衆が多数いる。
各聴衆のシャイさをS[i]とする。
その聴衆は、他にS[i]人以上拍手をしていたら拍手をする。

S[i]の最大値をSmaxとする。
S[i]の値が0~Smaxの人数がそれぞれ与えられる。

全員に拍手をさせたいとき、既存の人数で足りなければ任意のS[i]を持つサクラを追加できる。
最小でサクラが何人いればよいか答えよ。

解法

S[i]=xの人数をP[x]とする。またサクラの人数をQとする。
S[i]=xの人が拍手するには Q + \sum_{i=0}^{x-1} P_iがi以上ならよい。
足りないならその分Qを追加する、という処理を繰り返せばよい。

void solve(int _loop) {
	int i,N;
	string S;
	
	cin>>N>>S;
	
	int sum=0,t=0;
	FOR(i,N+1) {
		if(sum<i) t+=i-sum,sum=i;
		sum+=S[i]-'0';
	}
	
	_P("Case #%d: %d\n",_loop,t);
}

まとめ

最初問題を適当に読んでたので、「(サクラ関係なく)拍手する人数を求めよ」かと思ってしまった。

広告を非表示にする