ARC091 F - Strange Nim

F - Strange Nim

面白い問題だったので記録。公式解説とはちょっと違う解法。

考察・解法

実験と観察

山同士は相互に干渉しないので、それぞれの山のGrundy数を求めることが目的になる。

注目している1つの山について、残っている石の数を $X$ 、その山が持つパラメータ $A_{i}, K_{i}$ を単に $A, K$ 、Grundy数を $G(X)$ と記す。「もう操作できない状態」のGrundy数が0であるとして、

$X \lt K$ のとき、 $G(X) = 0$ 。
$X \ge K$ のとき、 $G(X)$ は $G(X - \lfloor\frac{X}{K}\rfloor)$ から $G(X - 1)$ までに登場しない最小の非負整数。

である。

これがどのような値になるか実験してみる。そうすると、

$\lfloor\frac{X}{K}\rfloor$ が変化しない範囲では、 $G(X)$ は $0$ から $\lfloor\frac{X}{K}\rfloor$ までの値がある順序で繰り返される。例えば $X = 30, ..., 39$ の範囲では、 $G(X)$ は $3, 1, 0, 2$ の繰り返しになっている。
$X$ が $K$ の倍数のとき $G(X) = \frac{X}{K}$ となり、それまでの順序のある位置に $\frac{X}{K}$ が「挿入」される形で、それ以降はまた値が繰り返される。

というような性質がある。この性質を使えば、いくつかの方法でGrundy数が求められそうである。

求め方1：再帰で求める

1つ目の方法は、繰り返しの性質を用いた再帰である。 $X$ が $K$ の倍数でないとき、以下のように考えることができる。

f:id:betrue12:20181024211331p:plain

この考え方から、 $X$ が $K$ の倍数でないとき $G(X) = G(X - \frac{X}{K} - 1)$ であることが分かる。 $X = A$ から始めて、これを $X \lt K$ になるか $X$ が $K$ の倍数になるまで再帰的に繰り返すことで、 $G(X)$ を求めることができる。

この操作1回で、 $X$ はおよそ $\frac{K-1}{K}$ 倍になる。 $K$ が小さいとこれで十分間に合うが、 $K$ が大きいときにはいくら指数的に減っていくとはいえスピードが遅すぎて間に合わない。

計算量はおそらく $O(\log(\frac{A}{K}) / \log(\frac{K}{K-1}))$ であり、 $O$ の中身を単純計算すると $A = 10^{9}, K = 10^{5}$ のときにおよそ $9.2 \times 10^{5}$ となる。後で $N = 200$ が掛かることを考えると、 $K \le 10^{5}$ くらいが限度だろうと思われる。

※公式解法では、後述の「求め方2」は使わず、この求め方1をベースにさらに高速化の工夫をしている。

求め方2：順序への「挿入」をシミュレートする

求め方1の欠点を補うため、 $K$ が大きい時に使えるGrundy数の求め方を考える。

先述のように、 $G(X)$ の遷移はある順序で繰り返され、 $X$ が $K$ の倍数になるごとに、その順序のある位置に新しい値が挿入される。これを全てシミュレートしてやることでも $G(X)$ を求めることができる。

やりたいのは、数列のどこかのインデックス（ $k$ 番目）へ値を挿入すること。そして、最後にどこかのインデックスの値を取ること。これは平衡二分木を使えば、要素数を $a$ として $O(\log a)$ で実現できる。

この操作は全部でおよそ $\frac{A}{K}$ 回行われるので、計算量は $O(\frac{A}{K} \log( \frac{A}{K}))$ である。これは求め方1とは逆に $K$ が大きいほど計算量が少なくなり、 $K \ge 10^{5}$ くらいであれば十分高速である。

解法まとめ

山ごとにGrundy数を求める。このとき、の値によって2通りの求め方を使い分ける。
1. $K$ が小さい場合、再帰で求める。
2. $K$ が大きい場合、順列への値の挿入を平衡二分木でシミュレートして求める。
全ての山のGrundy数のXORを取り、勝敗を判定する。

ACコード

Submission #3462224 - AtCoder Regular Contest 091

求め方を切り替える閾値の設定が難しく、 $10^{4}$ で分けた場合は TLEした。求め方1は処理がとても単純なので定数倍が軽く、求め方2では平衡二分木の処理が重いので、単純に $O$ の中身を計算して比較したときの閾値より高めにするのがよい。想定解法ではないので、どう調整しても通らないときは仕方がない。