自力で解いたものの微妙に手間取った。
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; } }
まとめ
これはシンプルでなかなか良い問題だった。