37.50.48

%20 の ブログ

yukicoder No.1852 Divide or Reduce

この記事は yukicoder No.1852 Divide or Reduce の解説です。

操作 Y が行えない状況の場合、山同士は互いに影響を与えない、独立したゲームです。
独立したゲーム(二人で交互に操作する手番が来るようなゲーム)が複数ある場合、その状況に対する Grundy 数は、独立したそれぞれのゲームに対する Grundy 数たちの bitwise xor( \(\oplus\) で表します。)によって計算できます。
列 \(a\) に対し、操作 Y が行えないと仮定した場合の(嘘の)Grundy 数を \(g(a) = g(a_1) \oplus g(a_2) \oplus \cdots \oplus g(a_{|a|})\) と表すことにします。
列 \(a\) に対し、操作 Y も考慮した本当の Grundy 数を \(G(a)\) と表すことにします。

  • \(G(a) \ne 0\) ならば手番のプレイヤーが勝ち
  • \(G(a) = 0\) ならば手番のプレイヤーが負け

です。
よって、初期状態の列 \(A\) に対する Grundy 数 \(G(A)\) が \(0\) かどうかが分かればよいということになります。

\(\mathrm{mex}\) を(可変個の)引数に含まれない最小の非負整数を返す関数とします。
\(g\) について計算してみると、

  • \(g(1) = \mathrm{mex}(\emptyset) = 0\)
  • \(g(2) = \mathrm{mex}(g(1) \oplus g(1)) = \mathrm{mex}(0) = 1\)
  • \(g(3) = \mathrm{mex}(g(1) \oplus g(2)) = \mathrm{mex}(1) = 0\)
  • \(g(4) = \mathrm{mex}(g(1) \oplus g(3), g(2) \oplus g(2)) = \mathrm{mex}(0,0) = 1\)
  • \(g(5) = \mathrm{mex}(g(1) \oplus g(4), g(2) \oplus g(3)) = \mathrm{mex}(1,1) = 0\)
  • \(\vdots\)

のようになり、

  • \(g(奇数) = 0\)
  • \(g(偶数) = 1\)

であることが分かります。

  • \(\min(A) = 1\) のとき
    • 操作 Y はできないので、初期状態の列 \(A\) に対し、\(G(A) = g(A)\) です。
    • よって、どちらが勝つか分かります。
  • \(\min(A) \gt 1\)のとき
    • \(g(A) = 1\) のとき
      • 操作 X を行い、操作後の列 \(A'\) が \(g(A') = 0\) を満たすようにできます。
      • さらに、操作対象の \(A_i\) を \(A_i-1\) と \(1\) に分割することによって \(\min(A') = 1\) にできるので、\(G(A') = g(A') = 0\) を満たすようにすることができます。
      • \(G(A') = 0\) となるように操作できる状態だったので、初期状態に対する Grundy 数は \(G(A) \ne 0\) であったことが分かります。
    • \(g(A) = 0\) のとき
      • 操作 X を行うと、操作後の列 \(A'\) は \(g(A') = 1\) を満たします。\(g(A') = 1\) のとき \(G(A') \ne 0\) なので、これは相手を勝たせてしまう操作になります。
      • ということで、操作 Y を行うのが最善です。操作 Y を行うと列の要素のそれぞれが偶奇反転されます。
      • 素数 \(|A|\) が奇数のとき
        • 必ず \(g(A') = 1\) になるので \(G(A) = 0\) です。
      • 素数 \(|A|\) が偶数のとき
        • \(g(A') = g(A) = 0\) なので、手番の人が操作 Y を行うことを \(\min(A)-1\) 回繰り返すことになります。
        • ということで、\(\min(A)\) の偶奇が分かればよいです。
          • \(\min(A)\) が偶数のとき、\(G(A) \ne 0\)
          • \(\min(A)\) が奇数のとき、\(G(A) = 0\)
        • です。

\(\min(A) \gt 1\) を満たす入力しか来ないつもりで実装しても、\(\min(A) = 1\) の場合も上手くいきます。

実装例(C++17)