yukicoder No.78 クジ付きアイスバー

制約が大きいので愚直にシミュレーションすると通らない……はずなのだけど、Cは速いからギリギリ通っちゃうんだなこれが

char box[60];
int n,k,cost,stock,p;
int main(){
	scanf("%d%d%s",&n,&k,box);
	while(k--){
		if(stock>0)stock--;else cost++;
		stock+=box[p]-'0';
		p++;
		if(p==n)p=0;
	}
	printf("%d",cost);
	return 0;
}

stockは高々k+1にしかならないのでオーバーフローの心配はない

ちゃんとやるならこういう感じになるだろうか
☆☆☆☆☆☆
以下「当たり棒の数」と言えば「当たり棒によって貰える本数」を指すものとする（つまり「２本当たり１つ」は「２」と数える）
当たり棒を持っているとき、必ずしもそれを使わなくてもよいことに注意する（最終的に無駄なく使えれば良いので）
１箱目をシミュレーションする。
１箱目で買う本数をx、１箱目終了時点でストックされている当たり棒の数をyとする。
２箱目ではストックされている当たり棒を、「１箱目で買う必要があったアイス」の後ろから割り当てることを考える。
x≦yのときはストックされている当たり棒を使い切ることなく２箱目を買い尽くせてしまう。当然２箱目終了時点でストックされている当たり棒の数はy以上になるので、これ以降最後まで買うことはない。
x＞yのときはストックを使い尽くすことができ、２箱目終了時点でストックされている当たり棒の数は１箱目と同じくyとなる。よって以降全く同じ状況でループするので箱買い部分はまとめて処理し、最後に余った部分をシミュレーション

char box[60];
n,k,x,y;
void hakogai(){
	int stock=0,cost=0,i;
	for(i=0;i<n;i++){
		if(stock>0)stock--;else cost++;
		stock+=box[i]-'0';
	}
	x=cost;
	y=stock;
}
int hasuu(int rest,int stock){
	int cost=0,i;
	for(i=0;i<rest;i++){
		if(stock>0)stock--;else cost++;
		stock+=box[i]-'0';
	}
	return cost;
}
int main(){
	scanf("%d%d%s",&n,&k,box);
	if(k<n)printf("%d",hasuu(k,0));
	else {
		hakogai();
		if(x<=y)printf("%d",x);
		else printf("%d",x+(x-y)*(k/n-1)+hasuu(k%n,y));
		//１箱目でx本買い、２箱目以降はストックがy本あるので(x-y)本買う
	}
	return 0;
}

☆☆☆☆☆☆

閑話休題

縮める

char b[60];
c,s,p;
main(n,k){
	for(scanf("%d%d%s",&n,&k,b);k--;p%=n)s?s--:c++,s+=b[p++]-48;
	c=!printf("%d",c);
}

とするとTLE　……えっ

どうやら剰余を取る部分が重かったらしい。ここを素直に書き直して

char b[60];
c,s,p;
main(n,k){
	for(scanf("%d%d%s",&n,&k,b);k--;p*=p!=n)s?s--:c++,s+=b[p++]-48;
	c=!printf("%d",c);
}

109B

メモ

yukicoderでゆるふわgolf

yukicoder No.78 クジ付きアイスバー