Xmas Contest 2020 C: Candies Candidates 解説

https://atcoder.jp/contests/xmascon20/tasks/xmascon20_c

問題概要

数列中の正の整数 $x$ を $x-1$ または $\left\lfloor\frac{\sqrt{5}-1}{2} x\right\rfloor$ に変えられるゲームがある．与えられた数列が先手必勝か後手必勝か判定せよ．

とりあえず

値が減っていく不偏ゲームなので (short impartial game なので)，各皿の Grundy 数を考えて XOR をとればよいです．

行動が $2$ 通りしかないので Grundy 数も高々 $2$ までしか登場しません．が，これ以上は見て直ちにわかることはないので，実験しましょう．

解法 1 (観察)

実験して出てきた $0, 1, 2$ の列をぐっとにらむと，再帰的構造が見えてくるかもしれません．

解法 2 (OEIS)

$0, 1, 2$ の列を OEIS に入れても出てこない (2020 年 12 月現在) のですが，Grundy 数がそれぞれ $0, 1, 2$ になる値の列はなんと出てきます：

これらのタイトル通りに実装すると (あるいは解法 1 でもそうかもしれませんが) 小数計算が必要になります．整数と整数の比は黄金比にかなり近くなりうるので (隣接する Fibonacci 数)， $\left(\frac{1 + \sqrt{5}}{2}\right)^2$ などを求める時点でかなりの精度が要求されます．Java の BigDecimal や Python の Decimal などを用いて正解できます．

解法 3 (Zeckendorf representation)

よく見ると上の $1$ の OEIS にもちらっと書いてあるのですが，Zeckendorf representation，いわゆる Fibonacci 進法を考えるとうまくいきます．任意の非負整数は相異なる隣接しない Fibonacci 数の和の形に一意に表すことができ，その表示は大きいほうから貪欲にとっていくことで求められます．この表示と Grundy 数を並べて出力してみると，以下のことに気づくことができると思います．

Grundy 数が $0$ ： $0$ または，用いる最小の Fibonacci 数が $2, 5, 13, 34, \ldots$ (Fibonacci 進法で末尾の $0$ が奇数個)
Grundy 数が $1$ ：用いる最小の Fibonacci 数が $1$ (Fibonacci 進法で末尾が $1$ )
Grundy 数が $2$ ：用いる最小の Fibonacci 数が $3, 8, 21, 55, \ldots$ (Fibonacci 進法で末尾の $0$ が正の偶数個)

証明

Fibonacci 数を $F_0 = 0,\, F_1 = 1,\, F_i = F_{i-1} + F_{i-2}$ とします． $g = \frac{1+\sqrt{5}}{2},\, h = \frac{1-\sqrt{5}}{2}$ とおいて， $F_i = \frac{1}{\sqrt{5}} (g^i - h^i)$ です．

$x \ge 1$ の Zeckendorf representation の形で場合分けして $x - 1$ と $\left\lfloor\frac{x}{g}\right\rfloor$ の表示を求めます．以下 $F_j + \cdots$ の部分は番号が大きい部分の隣接しない Fibonacci 数の有限和とします (丁寧に書くと煩雑なので許してください)．

偶数 $i \ge 4$ に対し $x = F_i + F_j + \cdots$ のとき， $x - 1 = F_3 + F_5 + \cdots + F_{i-1} + F_j + \cdots$
奇数 $i \ge 3$ に対し $x = F_i + F_j + \cdots$ のとき， $x - 1 = F_2 + F_4 + \cdots + F_{i-1} + F_j + \cdots$
$i \ge 4$ に対し $x = F_2 + F_i + F_j + \cdots$ のとき， $x - 1 = F_i + F_j + \cdots$

これらはすぐわかると思います ( $1$ に $F_3, F_5, \ldots$ あるいは $F_2, F_4, \ldots$ を順に足してみてください)．

偶数 $i \ge 4$ に対し $x = F_i + F_j + \cdots$ のとき， $\left\lfloor\frac{x}{g}\right\rfloor = F_2 + F_4 + \cdots + F_{i-2} + F_{j-1} + \cdots$
奇数 $i \ge 3$ に対し $x = F_i + F_j + \cdots$ のとき， $\left\lfloor\frac{x}{g}\right\rfloor = F_{i-1} + F_{j-1} + \cdots$
$i \ge 4$ に対し $x = F_2 + F_i + F_j + \cdots$ のとき， $\left\lfloor\frac{x}{g}\right\rfloor = F_{i-1} + F_{j-1} + \cdots$

これらはすぐわからないと思いますので示していきます． ${} + \cdots$ の部分も番号が $1$ ずつ小さくなります．

$a = F_{i-1} + F_{j-1} + \cdots,\, b = F_i + F_j + \cdots$ とおくと，

$\begin{align} b - g a &= \frac{1}{\sqrt{5}} ( ( (g^i - h^i) - g (g^{i-1} - h^{i-1}) ) + ( (g^j - h^j) - g (g^{j-1} - h^{j-1}) ) + \cdots) \\ &= \frac{1}{\sqrt{5}} ( ( h^{i-1} (g - h) ) + ( h^{j-1} (g - h) ) + \cdots) \\ &= h^{i-1} + h^{j-1} + \cdots \end{align}$

となります． $-1 \lt h \lt 0$ なので，気持ちとしては， $h$ の累乗は符号を変えながら指数的に減っていくので，一番小さい番号の部分に支配されその偶奇で符号が決まります．

$i \ge 4$ が偶数のとき，

$\begin{align} h^{i-1} + h^{j-1} + \cdots &\gt h^{i-1} +\sum_{k=0}^\infty h^{i+2k+1} = h^{i-1} + \frac{h^{i+1}}{1 - h^2} = -h^{i-2} \ge -h^2, \\ h^{i-1} + h^{j-1} + \cdots &\lt h^{i-1} +\sum_{k=0}^\infty h^{i+2k+2} = h^{i-1} + \frac{h^{i+2}}{1 - h^2} = -h^i \lt 0 \end{align}$

より $-h^2 \lt b - g a \lt 0$ です．これより， $a - 1 \lt a - \frac{h^2}{g} \lt \frac{b}{g} \lt a$ および $a \lt a + \frac{1-h^2}{g} \lt \frac{b+1}{g} \lt a + \frac{1}{g} \lt a + 1$ が従い， $\left\lfloor\frac{b}{g}\right\rfloor = a - 1,\, \left\lfloor\frac{b+1}{g}\right\rfloor = a$ が得られました．

$i \ge 3$ が奇数のとき，

$\begin{align} h^{i-1} + h^{j-1} + \cdots &\gt h^{i-1} +\sum_{k=0}^\infty h^{i+2k+2} = h^{i-1} + \frac{h^{i+2}}{1 - h^2} = -h^i \gt 0, \\ h^{i-1} + h^{j-1} + \cdots &\lt h^{i-1} +\sum_{k=0}^\infty h^{i+2k+1} = h^{i-1} + \frac{h^{i+1}}{1 - h^2} = -h^{i-2} \lt -h \end{align}$

より $0 \lt b - g a \lt -h$ です．これより， $a \lt \frac{b}{g} \lt \frac{b+1}{g} \lt a + \frac{1-h}{g} = a + 1$ が従い， $\left\lfloor\frac{b}{g}\right\rfloor = a,\, \left\lfloor\frac{b+1}{g}\right\rfloor = a$ が得られました．

以上で $\left\lfloor\frac{x}{g}\right\rfloor$ の表示は証明できました．これを用いると，元の問題の Grundy 数についての主張は帰納法で示されます．

統計情報

正解者：チーム korotkevin (0:19:32) はじめ 47 チーム

簡単な設定で黄金比が登場する Wythoff's game というゲームがよく知られています．ではゲームに黄金比を直接登場させてみるとどうなるか？という動機で問題を作ってみました．Fibonacci 進法で書いてみたらちょうどよい複雑さになっていてびっくりでした．Wythoff's game や OEIS 解に登場している Beatty sequence や Wythoff sequence といった，非負整数全体の分割が無理数や floor によって綺麗に表されるという構造が，組合せゲームとの相性がよいようですね．