問題はこちら
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