Official

E - XY Game Editorial by sounansya

このゲームは二人零和有限確定完全情報ゲームなので、各山に対する Grundy 数が求まれば良いです。以降石が \(v\) 個の山に対する Grundy 数を求めることを考えます。

また、 \(v\) が \(X\) または \(Y\) の倍数である場合は Alice の最初の手を考えることで \(v\) が \(X\) の倍数でも \(Y\) の倍数でもない場合の（\(2\) つ以下の）問題に帰着させることができます。したがって、以降は \(v\) が \(X\) の倍数でも \(Y\) の倍数でもない場合を考えます。

\(Y\) が \(X\) の倍数である場合は簡単な規則性があります。具体的には、Grundy 数は以下のように計算することができます。

  • \(X\equiv 0\bmod 3\) のとき：
    • Grundy 数は \((v - 1) \bmod 3\) となる。
  • \(X\equiv 1\bmod 3\) のとき：
    • Grundy 数は \(((v \bmod X) - 1) \bmod 3 \)となる。
  • \(X\equiv 2\bmod 3\) のとき：
    • \(v \equiv 0\bmod 3\) のとき、Grundy 数は \(2\) となる。
    • そうでないとき、Grundy 数は \((((v \bmod X) - 1) \bmod 3) \oplus (\left\lfloor\frac vX \right\rfloor \bmod 2)\) となる。

\(v\) が \(X\) の倍数となる状況は考えていないことに注意してください。証明は数学的帰納法を用いれば良いです。

\(v < Y\) であるような場合も実質的に上と同じ状況なので、上の式を元に Grundy 数を計算することができます。以降は \(Y\) が \(X\) の倍数ではなく、 \(Y < v\) となる状況についてのみ考えます。

\(S\) を到達不可能な石の数の集合、つまり \(S=\lbrace nX | n \in \mathbb{N}_{\geq 0}\rbrace \cup\lbrace nY | n \in \mathbb{N}_{\geq 0}\rbrace \) とします。

\(a \le b \) に対し \(a,b\in S\) 、\(a+1,a+2,\ldots,b-1 \not \in S\) となるとき、 \((a,b)\) を 区間 と呼びます。また、区間の 長さ を \(b-a\) （実際の長さと \(1\) ズレていることに注意してください）、区間の 値 を \((b - a) \bmod 3\) として定義します。

まず、区間の中の Grundy 数は順番に 012012… または 102102… のどちらかとなります。

例えば、\(X=5,Y=7\) の場合 Grundy 数は順に以下のようになります（\(X\) または \(Y\) の倍数となる箇所は x で表しています）：

0120x1x01x012xx0120xx012x01x0x1021x…

各区間では 0120 1 01 012 0120 012 01 0 1021 のように Grundy 数が規則的に並んでいることが分かります。

また、ある区間の Grundy 数の並びから次の区間の Grundy 数の並びは以下のように求めることができます：

  • 区間の値が \(0\) のとき：前の並びと変わらない。つまり、 012… なら 012… のままで、102… なら 102… のままとなる。
  • 区間の値が \(1\) のとき： 012… となる。つまり、012… でも 102… でも 012… となる。
  • 区間の値が \(2\) のとき： 前の並びと逆転する。つまり、 012… なら 102… となり、102… なら 012… となる。

つまり、 \(v\) 個の石の山の Grundy 数を求めるためにはその箇所より左側にある最も近い値が \(1\) の区間を探し、そこから右に値が \(2\) となるような区間がいくつあるかを求めることができれば良いです。

Grundy 数をもう少し高速に計算するために、以下のような方法で計算することを考えます。

  • \(X\) の倍数で区間を区切っていくことを考える。
  • さらにそこに \(Y\) の倍数で切り込みを入れ、区間の並びを完成させる。 \(X < Y\) より、元々あった区間にある \(Y\) の倍数の個数は高々 \(1\) 個である。

この考えを用いることで、例えば \(X << Y\) が成り立つ時に区間の長さが \(X\) であるような区間が大量に連続する場所をまとめて処理することができます。この考えを元にこの問題を解いていきます。

1. \(X\equiv 0\bmod 3\) のとき

\(Y\equiv 0 \bmod 3\) なら Grundy 数は \((v - 1) \bmod 3 \) です。以降は \(Y \not\equiv 0\bmod 3\) となる場合を考えます。

\(Y\) により区切られる \(2\) つの区間の値は 0 / 0 、1 / 2、2 / 1 のいずれかです。0 / 0 の場合は特に変化はないですが、それ以外の場合は値が \(1\) となる区間が必ず現れるため、そこを起点に Grundy 数を計算することができます。

\(kY\) により区切られた \(2\) つの区間の値が 0 / 0 なら \((k-1)Y\) により区切られた \(2\) つの区間の値は 0 / 0 以外になるので、大きい方から \(2\) つ調べれば良いです。

2. \(X\equiv 1\bmod 3\) のとき

\(Y > 2X\) または \(Y\equiv 0 \bmod 3 \) である場合連続する \(4\) つの区間のうち \(1\) つ以上は値が \(1\) です。したがって、 \(Y < 2X\) かつ \(Y\not\equiv 0\bmod 3\)の場合を考えます。

\(Y\) により区切られる前の \(X\) のみによって区切られた区間の値は \(1\) なので、 \(\displaystyle \frac{Y}{X}\) が \(1\) よりある程度大きい場合は愚直にシミュレーションすることで早い段階で値が \(1\) である区間に到達することができます。\(\displaystyle \frac{Y}{X}\) が \(1\) に近い場合も \(Y\) により区切られた区間の左側の長さが段々減少していくので、その到達先を計算してまとめてスキップすることですぐに値が \(1\) である区間に到達することができます。

3. \(X\equiv 2\bmod 3\) のとき

\(kY\) により区切られる \(2\) つの区間の値は 0 / 2 、1 / 1、2 / 0 のいずれかです。\(kY\) により区切られる左側の区間の左端は \(\displaystyle X\left\lfloor \frac {kY}X \right\rfloor\) なので、\(kY\) により区切られる \(2\) つの区間の値が 1 / 1 になる条件は \(\displaystyle kY - X\left\lfloor \frac {kY}X \right\rfloor \equiv 1\bmod 3\) と書くことができます。 \(\displaystyle c=\left\lfloor \frac YX \right\rfloor\) とすると、条件は \(\displaystyle (Y+c)k +\left\lfloor \left(\frac {Y}X-c\right)k \right\rfloor \equiv 1\bmod 3\) となります。

3 - A. \(Y+c\equiv 0\bmod 3\) のとき

条件は \(\displaystyle \left\lfloor \left(\frac {Y}X-c\right)k \right\rfloor \equiv 1\bmod 3\) となります。 \(\displaystyle 0 < \frac {Y}X-c < 1\) が成り立つので、条件と \(\displaystyle kY < v\)が成り立つ最大の \(k\) は簡単に計算することができます。

3 - B. \(Y+c\equiv 1\bmod 3\) のとき

条件は \(\displaystyle k+\left\lfloor \left(\frac {Y}X-c\right)k \right\rfloor \equiv 1\bmod 3\) となります。

条件を満たす \(k\) を \(k\) としてあり得る最大値（\(\displaystyle v/Y\) あたり）から順に探索して見つからない場合、\(\displaystyle \left(k+\left\lfloor \left(\frac {Y}X-c\right)k \right\rfloor \right) \bmod 3\) の値は \(0\) と \(2\) を繰り返しています。したがって、 \(k=2k'+k_0\) （\(k_0 \in \lbrace 0,1\rbrace\)） として \(k\) の偶奇で分けて考えて、 \(\displaystyle \left\lfloor \left(\frac {2Y}X-2c-1\right)k'+\left(\frac {Y}X-c\right)k_0\right\rfloor \bmod 3\) の値が変わる境目をそれぞれ計算すれば良いです。

3 - C. \(Y+c\equiv 2\bmod 3\) のとき

条件は \(\displaystyle \left\lfloor \left(\frac {Y}X-c-1\right)k \right\rfloor \equiv 1\bmod 3\) となります。 \(\displaystyle -1 < \frac {Y}X-c-1 < 0\) が成り立つので、条件と \(\displaystyle kY < v\)が成り立つ最大の \(k\) は簡単に計算することができます。

以上の議論より \(v\) 個の山に対する Grundy 数が \(O(1)\) で計算できることが分かります。

以上を適切に実装することでこの問題に正答することができます。計算量はテストケースあたり \(O(N)\) です。

実装では端点の扱いなどに注意してください。

posted:
last update: