ちょっと難しかったけど面白かった。
https://www.hackerrank.com/contests/unkoder-07/challenges/majority-cards
問題
白と黒の計N枚からなるカードの山がある。
この山の上からK枚(奇数)を取り、白と黒の多い方を1枚だけ山の一番下に戻す、という処理を繰り返す。
最終的に黒が1枚残るようにしたい。
条件を満たす山の初期状態のうち、黒の最小枚数を求めよ。
解法
色々な解法がありそうな問題。
テストケースがかなりのヒントになっている。
カードを上から(K^(m-1))枚ずつK個の組からなると考えた場合、先頭(K+1)/2個の組が最終的に黒1枚、後ろ(K-1)/2個の組は最終的に白になれば、最終的に全体が黒1枚になる。
例えば、K=3とすると、m=1,2,3,4の時の条件を満たすカードの並びは以下のようになる。(*:黒 .:白)
下記パターンをP[m]とする。
.
.**....
.**....**.**.............
カードがT=K^m枚より多く、K^(m+1)枚より少ない場合を考える。 この場合、先頭の(N-T)/(K-1)*K枚について、(N-T)/(K-1)回カードの山を取った結果、残りのT-(N-T)/(K-1)枚と新たに追加された(N-T)/(K-1)枚のカードによって、P[m]の状態ができる。 よって、元のカードの先頭(N-T)/(K-1)*Kから生成した(N-T)/(K-1)枚がP[m]の下(N-T)/(K-1)枚、元のカードの後ろT-(N-T)/(K-1)枚がP[m]の上T-(N-T)/(K-1)枚になると考え、それぞれ再帰的に黒カードの枚数を求めればよい。.**....**.**.............**.**....**.**........................................
|ll N,K; ll pat[100]; ll lower(ll v,ll T,int m) { if(v==0) return 0; ll p=v/(T/K), r=v%(T/K); if(p>=K/2) return (p-(K/2))*pat[m-1] + lower(r,T/K,m-1); return 0; } ll upper(ll v,ll T,int m) { if(v==0) return 0; ll p=v/(T/K), r=v%(T/K); ll ret=min(p,(K+1)/2)*pat[m-1]; if(p<(K+1)/2) ret += upper(r,T/K,m-1); return ret; } void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>K; if(N==1) return _P("1\n"); int m=0; ll T=1; pat[0]=1; while(T*K<=N) T*=K, pat[m+1]=pat[m]*((K+1)/2), m++; cout<<upper(T-(N-T)/(K-1),T,m) + lower((N-T)/(K-1),T,m)*((K+1)/2)<<endl; }まとめ
いつになったらコンテスト名通りのkuso問が出るんでしょうかね…。