Grundy 数がフラクタルっぽい構造を示していた！

問題へのリンク

問題概要

$N$ 個の石の山がある。各山には $A_{1}, \dots, A_{N}$ 個の石がある。先手と後手が交互に以下の操作を繰り返す。

山を一つ選ぶ。その山には石が $a$ 個あるとする。
その山の石の個数が $a-1$ 個または $\frac{\sqrt{5} - 1}{2}a$ 個となるように石を除去する

操作を行えなくなった方が負けである。双方最善尽くしたときにどちらが勝つか？

制約

(テストケース数) $\le 100$
$1 \le N \le 20$
$1 \le A_{i} \le 10^{18}$

考えたこと

まずは Grundy 数を実験で求めてみることにした。そうすると

0, 1, 0, 2, 1, 0, 1, 0, 2, 1, 0, 2, 1, 0, 1, 0, 2, 1, 0, 1, 0, 2, 1, 0, 2, 1, 0, ...

となっていた。これを見てチームメイトの opt さんが、(1, 0) と (2, 1, 0) をそれぞれ 1, 2 と表せますか、と提案してきたのでやってみた。

1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 2, ...

これを見て opt さんはひらめいたようだ！！！　もしここからさらに、「2 の連続している個数」を列挙すると、ふたたび同じ数列になるようだ。確かにそうなっている。

そしてそのような数列は有名であり、一般項が次のように与えられると教えてくれた ( $r = \frac{1 + \sqrt{5}}{2}$ とする)。

ある整数 $m$ を用いて $n = \lfloor mr^{2} \rfloor$ と表せるとき、1
それ以外のとき、2

今回はちょっと違う数列なのでこのまま答えではない。でもよくみると、

0, 1, 0, 2, 1, 0, 1, 0, 2, 1, 0, 2, 1, 0, 1, 0, 2, 1, 0, 1, 0, 2, 1, 0, 2, 1, 0, ...
1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 2, ...

とを比較すると、もとの数列の 0 と、変換後の数列の 1 の index は一致している。そして 1 の位置は 1 だけズレているだけなのだ。よって、Grundy 数は、次のように求められることがわかった。

$n = \lfloor mr^{2} \rfloor$ と表せるとき、0
$n = \lfloor mr^{2} \rfloor - 1$ と表せるとき、1
それ以外のとき、2

あとはこれを実装すれば OK。ただし $r$ の計算に long double 型を用いても精度が足りないので、 $10^{50}$ 倍して整数計算にして強引に通した。

でも Python なら Decimal 型でできるね。

コード

from decimal import *
getcontext().prec = 100

r2 = (Decimal.sqrt(Decimal(5)) + Decimal(3)) / Decimal(2)

def Grundy(n):
    m = int(Decimal(n) / Decimal(r2))
    for m2 in range(m-3, m+3, 1):      
        g = int(Decimal(m2) * Decimal(r2))
        if n == g:
            return 0
        elif n == g - 1:
            return 1
    return 2

T = int(input())
for _ in range(T):
    N = int(input())
    A = list(map(int, input().split()))
    res = 0
    for a in A:
        res ^= Grundy(a)
    print('Black' if res > 0 else 'White')

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

Xmas Contest 2020 C - Candies Candidates

問題概要

制約

考えたこと

コード