ARMERIA

放置していたけど更新再開、Rubyと競技プログラミングの話が中心になっていく予定です

ARC091 F - Strange Nim

F - Strange Nim

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

考察・解法

実験と観察

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

注目している1つの山について、残っている石の数を  X 、その山が持つパラメータ  A_{i}, K_{i} を単に  A, KGrundy数を  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} くらいであれば十分高速である。

解法まとめ

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

ACコード

Submission #3462224 - AtCoder Regular Contest 091

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

さいごに

一番最後はデータ構造で「殴って」しまったけれど、Grundy数の一見不規則に見えて実は美しい規則性、計算量の落とし方の工夫、ともに面白い問題だった。