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); } }
まとめ
本番周期性ではダメなことに気づけて良かった。
というか実験でわかった。