Codeforces Round #334 (Div. 1) C. Lieges of Legendre

問題はCodeforces Round #334 (Div. 2) のE問題と同じです。

問題文

codeforces.com

問題概要

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数の分裂を知っていないときつい問題。