yukicoder : No.1651 Removing Cards

自力で解いたものの微妙に手間取った。
https://yukicoder.me/problems/no/1651

問題

正整数N,Kが与えられる。
1～Nが書かれたカードが1列に並んでいる。
カードが1枚になるまで、以下を繰り返す。

• 先頭からiK+1枚目のカードを同時に取り除く

最後に残るカードは、どの数字が書かれたカードか。

解法

f(s) := カードが残り1枚になるまで、s回処理が必要となる最小カード枚数
とする。解はf(s)≦Nである最大のsにおけるf(s)である。

そこで事前にf(s)を列挙しておけば、様々なNに対し適切なsを二分探索できる。
f(s+1)は、1回処理を行うとf(s)枚残る最小のカード枚数なので、やはり二分探索などで求めることができる。

int K,Q;
ll N;

ll pat[10000000];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>K>>Q;
	
	pat[0]=0;
	pat[1]=1;
	for(i=2;i<=1000000;i++) {
		if(pat[i-1]>=1LL<<60) {
			pat[i]=pat[i-1]+1;
		}
		else {
			ll p=2LL<<60;
			for(j=60;j>=0;j--) {
				ll tmp=p-(1LL<<j);
				ll tmp2=tmp-(tmp+K-1)/K;
				if(tmp2>=pat[i-1]) p=tmp;
			}
			pat[i]=p;
		}
	}
	
	
	while(Q--) {
		cin>>N;
		x=(lower_bound(pat,pat+1000000,N+1)-pat);
		cout<<pat[x-1]<<endl;
	}
	
}

まとめ

これはシンプルでなかなか良い問題だった。