Codeforces Round #334 (Div. 1) C. Lieges of Legendre
問題はCodeforces Round #334 (Div. 2) のE問題と同じです。
問題文
問題概要
n個のコインの山があり、それぞれの山iにはa[i]枚のコインがある。KevinとNickyは交互に以下の操作のいずれかを行う。
- 山を1つ選び、その山からコインを1枚取り除く
- コインが偶数枚(2x枚)ある山を1つ選び、その山をコインがx枚あるk個の山に置き換える
操作を行えなくなったプレイヤーが負けとなる。両者が最善手を打ったときどちらが勝つだろうか。
解法
山に$n$枚のコインがあるときのGrundy数を$g(n)$と表し、$\langle a_1,\ldots,a_n \rangle$と書いたら整数集合$\{a_1,\ldots,a_n\}$に含まれない最小の非負整数を表すものとする。
Grundy数の性質により、$g(n)$は以下の漸化式に従う
\[ g(n)= \cases{ \langle g(n-1) \rangle & \text{($n$が奇数)} \\ \langle g(n-1),\underbrace{g(n/2) \oplus \cdots \oplus g(n/2)}_{k個} \rangle & \text{($n$が偶数)} } \]
xorの性質から次の等式が成り立つ。
\[ \underbrace{g(n/2) \oplus \cdots \oplus g(n/2)}_{k個}= \cases{ g(n/2) & \text{($k$が奇数)} \\ 0 & \text{($k$が偶数)} } \]
これを用いると先ほどの漸化式は次のようになる。
(1)$k$が奇数のとき
\[ g(n)= \cases{ \langle g(n-1) \rangle & \text{($n$が奇数)} \\ \langle g(n-1),g(n/2) \rangle & \text{($n$が偶数)} } \]
(2)$k$が偶数のとき \[ g(n)= \cases{ \langle g(n-1) \rangle & \text{($n$が奇数)} \\ \langle g(n-1),0 \rangle & \text{($n$が偶数)} } \]
$1 \le n \le 10^9$なので、動的計画法やメモ化再帰で計算するのは難しい。考察をより進める。
(1)$k$が奇数のとき
$g(0)$から$g(10)$までを列挙すると次のようになる。
$n$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|---|
$g(n)$ | 0 | 1 | 0 | 1 | 2 | 0 | 2 | 0 | 1 | 0 | 1 |
$n$が十分大きい奇数ならば$g(n)=0$が成り立つことがわかる。そのため$g(n)$は次のように表せる。
\[ g(n)= \cases{ 0 & \text{($n=0$)} \\ 1 & \text{($n=1$)} \\ 0 & \text{($n=2$)} \\ 1 & \text{($n=3$)} \\ 2 & \text{($n=4$)} \\ 0 & \text{($n$が奇数)} \\ \langle 0,g(n/2) \rangle & \text{(その他)} } \]
これは$O(\log n)$で計算できる。
(2)$k$が偶数のとき
$g(0)$から$g(10)$までを列挙すると次のようになる。
$n$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|---|
$g(n)$ | 0 | 1 | 2 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
$n$が十分に大きいならば$g(n)=(n-1)\bmod 2$が成り立つことがわかる。そのため$g(n)$は次のように表せる。 \[ g(n)= \cases{ 0 & \text{($n=0$)} \\ 1 & \text{($n=1$)} \\ 2 & \text{($n=2$)} \\ (n-1)\bmod 2 & \text{(その他)} } \]
これは$O(1)$で計算できる。
あとはGrundy数の性質を使って勝敗を判定すればいい。
Codeforces Round #334 (Div. 1) C. Lieges of Legend ...
感想
Grundy数の分裂を知っていないときつい問題。