Hatena::Grouptopcoder

kohyatohの日記

 - 非数学系な人のTopCoder参加記です。

2012-03-29

Codeforces #114 C (Wizards and Numbers)

| 00:50

解けなかった&解法を見ても理解できなかったので復習。

問題文は

http://codeforces.com/problemset/problem/167/C

下のような思考をできれば解けたのではないかと思われる。


(a, b) (a<=b) で手番が回ってきたとき、勝てるか負けるかを考える。

(b%a, a)は(b-a^k, a)より考えやすいので、まずは(b%a, a)について考え場合分け。

(1) a==0 の場合

既に負け。


(2) (b%a, a) で相手に回して勝てる場合

勝ち。


(3) (b%a, a) で相手に回して負ける場合

どうやっても、どちらかの手番にいずれ(b%a, a)が現れること(※)に注意。

自分に(b%a, a)の手番を回すよう仕向けることが出来れば勝てる。

そうで無い場合、相手に(b%a, a)の手番が回るので、負ける。


(※の証明)

このターンで(b-a^k, a)にして相手に渡したとする。

この時、b-a^k < aならば、b-a^k == b%a。

b-a^k >= a ならb≡b-a^k (mod a) より帰納法で示せる。



(3)の、「自分に(b%a, a)の手番を回すよう仕向けることができる」のは、どんな場合?

(※)より、b-b%a == a^k1 + a^k2 + ... + a^kn となる。

(k1は自分の手、k2は相手の手、k3は自分の手...を表す)

自分がk1を選び、それを見て相手がk2を選び、...を繰り返して、

nを偶数にできるなら自分の勝ち、奇数にしかできないなら相手の勝ち。

(i) aが奇数の時

a^kも奇数。よって b-b%a ≡ a^k1 + a^k2 + ... + a^kn ≡ n (mod 2)

ゆえに、b-b%aが偶数ならば自分の勝ち、奇数ならば相手の勝ち。


(ii) aが偶数の時

b-b%aに、aがいくつ詰められるか、という観点で考える。

x = (b-b%a)/a (== floor(b/a)) について場合分けをして法則性がないか見る。

a <= b より x >= 1。

(あ) x == 1 の時

b-b%a = xa = a, よって相手の勝ち。


(い) x == 2 の時

b-b%a = xa = a+a, よって自分の勝ち。


(う) x == 3 の時

b-b%a = xa = a+a+a, よって相手の勝ち。

...

(わ) x == a の時

b-b%a = xa = a*a, よって自分の勝ち。(aは偶数であることに注意)


(を) x == a+1 の時

b-b%a = xa = a^2 + a, よって偶数にできるので自分の勝ち。


(ん) x == a+2 の時

b-b%a = xa = a + a^2 + a or a^2 + a + a

この時は、k1=1でもk1=2でもk2の選び方によりnを偶数にされてしまい、自分の負け。



(あ) ~ (ん) より、1<=x<=aでは相手勝ち/自分勝ちが交互に現れ、a+1<=x<=a+2では自分勝ち/相手勝ちが交互に現れることがわかる。


ここから、x%(a+1)が奇数ならば自分勝ち、偶数ならば相手勝ち、という仮説が導かれる。

一般の場合に、この仮説が正しいかを検証する。

a^2 - 1 ≡ (a+1)(a-1) ≡ 0 (mod a+1)

よって a^2 ≡ 1 (mod a+1) となることに注意。

よってmod a+1ではa^2≡1, a^3≡a, a^4≡1...となる。(<=この性質は覚えておいたほうがよさげ)


以下xをmod a+1で考える。

(1) x が奇数の時

xから1を引く(=bからaを引く)ことで、xを偶数にできる(xが偶数の状態で相手に手番を回せる)。

よって自分勝ち。


(2) x が偶数の時

xから1を引いても、aを引いても、xは奇数となる。

よって相手勝ち。


以上より、aが偶数の時、x%(a+1)の偶奇で勝敗が決まる、という仮説が証明された。

よって次のような関数を作れる。

bool win(long long a, long long b) {
    if (a == 0) return false;
    else if (!win(b%a, a)) return true;
    else {
        if (a%2) return (b-b%a) % 2 == 0;
        else return (b/a) % (a+1) % 2 == 0;
    }
}

ここで、a%2==1のとき(b-b%a) % 2 == (b/a)*a % 2 == (b/a) % 2 == (b/a) % (a+1) % 2であることを用いると、少し圧縮できる。

bool win(long long a, long long b) {
    if (a == 0) return false;
    else if (!win(b%a, a)) return true;
    else return (b/a) % (a+1) % 2 == 0;
}

これが答え。

計算量はユークリッドの互除法と同じでO(log(a))。