kmjp's blog

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

UnKoder #07 : Majority Cards

ちょっと難しかったけど面白かった。
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問が出るんでしょうかね…。