kmjp's blog

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

TopCoder SRM 664 Div1 Easy BearPlays

SRM664に参加。Easyで若干出遅れるも、正答率低目かつ2Chal取って久々のレート増。
6連続レート減合計340だったので、少し回復できてよかった。
赤い人のいない部屋で、8Chal狙えたけどServer Busyであまり取れず。
http://community.topcoder.com/stat?c=problem_statement&pm=13916

問題

2つの石の山があり、それぞれの石の数はA,Bである。

2つの石の山に対し、以下の処理を繰り返す。
2つの山のうち少ない数をX,多い方をYとする。
少ない方の数が倍になるよう、Yから石を移す。
すなわち処理後の石の数は2X, Y-Xとなる。

処理をK回行った後、少ない方の山の石の数はいくらか。

解法

定番テクとして、周期性を求めようとすると失敗する。
何気にこの処理の周期はO(K)のため、TLEとなる。

1回処理すると少ない方の山は石が倍になるわけだが、多い方はどうなるか考える。
実は2*Y % (X+Y) = Y-Xのため、大きい方も(mod X+Yを取ると)2倍になっていることがわかる。
すなわち、どちらの山も結局2倍しているだけである。

よって、Z=A^K (mod A+B)を求め、min(Z, A+B-Z)を答えればよい。
また、1回の処理で倍々するだけのため、A+Bが素数だと周期が(K-1)/2となることがわかる。

ll mo;
ll modpow(ll a, ll n) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

class BearPlays {
	public:
	int pileSize(int A, int B, int K) {
		mo=A+B;
		C=A*modpow(2,K)%mo;
		return min(C,T-C);
	}
}

まとめ

本番周期性ではダメなことに気づけて良かった。
というか実験でわかった。