Google Code Jam 2015 Qualification Round : A. Standing Ovation

今年も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の人が拍手するにはが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);
}

まとめ

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