kmjp's blog

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

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

なんか昔の問題が難易度変更で★3になってたりするので、扱っておく。
https://yukicoder.me/problems/no/78

問題

アイスバーが箱詰めされて売っている。
各箱にはA個のアイスバーがあり、順に食べたとき「ハズレ」「1本あたり」「2本あたり」のいずれであるかが与えられる。
計K個のアイスバーを食べたいとき、自分で買わなければいけないアイスバーは何本か。

解法

最初と最後を除けば、1箱食べきるときに買わなければいけないアイスバーの数は周期的になる。
よって周期を求めればよい。

ll N,K;
string S;
ll tot[100001];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	cin>>S;
	
	i=0; y=0;
	for(x=1;x<=N*10;x++) {
		if(y==0) i++, y++;
		tot[x]=i;
		y+=S[(x-1)%N]-'0'-1;
	}
	if(K<=N*10) return _P("%lld\n",tot[K]);
	
	ll dif=tot[N*8]-tot[N*7];
	ll a=(K/N)-7;
	return _P("%lld\n",tot[N*7+(K%N)]+a*dif);
	
}

まとめ

★2.5でもいい気はするけどね。