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

メモ

yukicoderで遊んでいる競プロゆるふわ勢

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

問題はこちら
No.78 クジ付きアイスバー - yukicoder

制約が大きいので愚直にシミュレーションすると通らない……はずなのだけど、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にしかならないのでオーバーフローの心配はない


ちゃんとやるならこういう感じになるだろうか
☆☆☆☆☆☆
以下「当たり棒の数」と言えば「当たり棒によって貰える本数」を指すものとする(つまり「2本当たり1つ」は「2」と数える)
当たり棒を持っているとき、必ずしもそれを使わなくてもよいことに注意する(最終的に無駄なく使えれば良いので)
1箱目をシミュレーションする。
1箱目で買う本数をx、1箱目終了時点でストックされている当たり棒の数をyとする。
2箱目ではストックされている当たり棒を、「1箱目で買う必要があったアイス」の後ろから割り当てることを考える。
x≦yのときはストックされている当たり棒を使い切ることなく2箱目を買い尽くせてしまう。当然2箱目終了時点でストックされている当たり棒の数はy以上になるので、これ以降最後まで買うことはない。
x>yのときはストックを使い尽くすことができ、2箱目終了時点でストックされている当たり棒の数は1箱目と同じく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));
		//1箱目でx本買い、2箱目以降はストックが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