1日9時間寝たい

本当は10時間寝たいです

ニム和とニム積の分配法則の証明

ニム和とニム積に関して分配法則が成り立ちます。

『石取りゲームの数学~ゲームと代数の不思議な関係~』(佐藤文広) にある証明とまったく同じです。それを補足しながら説明します。


非負整数全体 ($0$ 以上の整数全体) を $\mathbb{N}_0$ と書きます。

定義 (mex)

非負整数の有限な部分集合 $S \subseteq \mathbb{N}_0$ に対し $\mathrm{mex}(S)$ を $\mathrm{mex}(S) := \min(\mathbb{N}_0 \setminus S)$ と定める。

定義 (ニム和)

$a, b \in \mathbb{N}_0$ に対し $a$ と $b$ のニム和 $a \dot+ b$ を
$a \dot+ b := \mathrm{mex}\{a' \dot+ b, a \dot+ b' \mid 0 \le a' < a, 0 \le b' < b\}$ と定める。

定義 (ニム積)

$a, b \in \mathbb{N}_0$ に対し $a$ と $b$ のニム積 $a \dot\times b$ を
$a \dot\times b := \mathrm{mex}\{a' \dot\times b \dot+ a \dot\times b' \dot+ a' \dot\times b'\mid 0 \le a' < a, 0 \le b' < b \}$ と定める。

簡単のために$\{a' \mid 0 \le a' < a\}$ を $\{a' \}$ と書きます。

  • $\mathrm{mex}\{1, 2, 3\} = 0$

  • $\mathrm{mex}\{0, 1, 2, \dots, n - 1\} = n$

  • $\mathrm{mex}\{0, 1, 2, \dots, n - 1, n + 1\} = n$

  • $2 \dot+ 3 = \mathrm{mex}\{0 \dot+ 3, 1 \dot+ 3, 2 \dot+ 0, 2 \dot+ 1, 2 \dot+ 2\} = \mathrm{mex}\{3, 2,2, 3, 0\} = 1$

  • $a \dot+ 0 = \mathrm{mex}\{0 \dot+ 0, 1 \dot+ 0, \dots (a - 1) \dot+ 0\} = a$

  • $a \dot+ b = b \dot+ a$

  • $a_1 \dot+ b = a_2 \dot+ b \Rightarrow a_1 = a_2$

    • 対偶を示す。$a_1 < a_2$ としてよい。$a_2 \dot+ b = \mathrm{mex}\{a_2' \dot+ b, a_2 \dot+ b'\}$ だが $a_2'= a_1$ を考えると $a_1 \dot + b \in \{a_2' \dot+ b, a_2 \dot+ b'\}$ となるから $a_1 \dot+ b \ne a_2 \dot+ b$ である。
  • $a \dot+ a = 0$

    • $a = 0$ の場合成り立つ。上の式が成り立たない最小のものを $b > 0$ とする。$b \dot+ b = \mathrm{mex}\{b' \dot+ b, b \dot+ b'\} \ne 0$ より $b' \dot+ b = 0$ となる $0 \le b' < b$ がある。$b$ の最小性より $b' \dot+ b' = 0$ となり $b = 0$ が導かれて $b > 0$ に矛盾する。
  • $2 \dot\times 2 = 3$

    • (理由) 次の4つの mex だから。

      • $0 \dot\times 2 \dot+ 2 \dot\times 0 \dot+ 0 \dot\times 0 = 0$

      • $0 \dot\times 2 \dot+ 2 \dot\times 1 \dot+ 0 \dot\times 1 = 2$

      • $1 \dot\times 2 \dot+ 2 \dot\times 0 \dot+ 1 \dot\times 0 = 2$

      • $1 \dot\times 2 \dot+ 2 \dot\times 1 \dot+ 1 \dot\times 1 = 1$

  • $a \dot\times 0 = \mathrm{mex}(\emptyset) = 0$

  • $a \dot\times 1 = \mathrm{mex}\{a' \dot\times 1 \dot+ 0 \dot+ 0 \mid 0 \le a' < a\} = a$

  • $a \dot\times b = b \dot\times a$

$\mathrm{mex}$ は minimal excluded number (最小除外数) から来ています。
あとで使うので mex に関する補題を1つ示します。

補題

$S \subseteq T \subseteq \mathbb{N}_0$ かつ $\mathrm{mex}(S) \not\in T$ ならば $\mathrm{mex}(S) = \mathrm{mex}(T)$ である。

証明

$s < \mathrm{mex}(S) \Rightarrow s \in T$ だから $\mathrm{mex}(S) \not\in T$ ならば $\mathrm{mex}(T) = \mathrm{mex}(S)$
(理由?: そのような $s\ (0 \le s < \mathrm{mex}(S))$ は $s \not\in \mathbb{N}_0 \setminus T$ だから $\min(\mathbb{N}_0 \setminus T) \ge \mathrm{mex}(S)$ となり、$\mathrm{mex}(S) \in \mathbb{N}_0 \setminus T$ より等号が成り立つ)

分配法則

$\forall a, b, c \in \mathbb{N}_0$ に対し $(a \dot+ b) \dot\times c = a \dot\times c \dot+ b \dot\times c$

証明

$a', b, c$ などについては分配法則が成り立っているとします (帰納法の仮定)。

以下の式がすべて等しいです。

  1. $(a \dot+ b) \dot\times c$

  2. $\mathrm{mex}\{(a \dot+ b)' \dot\times c \dot+ (a \dot+ b) \dot\times c' \dot+ (a \dot+ b)' \dot\times c'\}$

  3. $\mathrm{mex}\{(a' \dot+ b) \dot\times c \dot+ (a \dot+ b) \dot\times c' \dot+ (a' \dot+ b) \dot\times c', (a \dot+ b') \dot\times c \dot+ (a \dot+ b) \dot\times c' \dot+ (a \dot+ b') \dot\times c'\}$

  4. $\mathrm{mex}\{(a' \dot\times c \dot+ a \dot\times c' \dot+ a' \dot\times c') \dot+ b \dot\times c, a \dot\times c \dot+ (b' \dot\times c \dot+ b \dot\times c' \dot+ b' \dot\times c')\}$

  5. $\mathrm{mex}\{(a \dot\times c)' \dot+ b \dot\times c, a \dot\times c \dot+ (b \dot\times c)'\}$

  6. $a \dot\times c \dot+ b \dot\times c$

[1] = [2] と [5] = [6] はそれぞれニム積、ニム和の定義どおりです。

[3] = [4] は帰納法の仮定と $x \dot+ x = 0$ などを使って整理すると分かります。

[2] = [3] を示しましょう。これができれば [4] = [5] も似たように示せます。[2] の $\mathrm{mex}($ここ$)$ を $S$ として、[3] の $\mathrm{mex}($ここ$)$ を $T$ とします。$S \subseteq T$ です。実際、$(a \dot+ b)' < a \dot+ b = \mathrm{mex}\{a' \dot+ b, a \dot+ b'\}$ だから

  • $(a \dot+ b)' = a' \dot+ b$

  • $(a \dot+ b)' = a \dot+ b'$

のどちらかです。よって $S \subseteq T$ です。あとは $((a \dot+ b) \dot\times c =)\ \mathrm{mex}(S) \not\in T$ を示せば上の補題から $\mathrm{mex}(S) = \mathrm{mex}(T)$ となります。つまり [2] = [3] です。

次の2つを示す必要がありますが、ほぼ同じなのでここでは1つ目だけ示します。

  • $(a \dot+ b) \dot\times c \ne (a' \dot+ b) \dot\times c \dot+ (a \dot+ b) \dot\times c' \dot+ (a' \dot+ b) \dot\times c'\ (0 \le a' < a, 0 \le c' < c)$ ★

  • $(a \dot+ b) \dot\times c \ne (a \dot+ b') \dot\times c \dot+ (a \dot+ b) \dot\times c' \dot+ (a \dot+ b') \dot\times c'\ (0 \le b' < b, 0 \le c' < c)$

等号が成り立つと仮定します (背理法)。いま $a' < a$ なので $a \dot+ b \ne a' \dot+ b$ です。

  • $a \dot+ b > a' \dot+ b$ のとき、$((a \dot+ b) \dot\times c =)\ $ ★の右辺 $\in S$ となり $(a \dot+ b) \dot\times c = \mathrm{mex}(S)$ に矛盾します。($\in$) の部分は $S$ で $(a \dot+ b)' = a' \dot+ b$ の場合を考えると分かります。

  • $a \dot+ b < a' \dot+ b$ のとき、★ (の $\ne$ を $=$ にしたもの) を
    $(a' \dot+ b) \dot\times c = (a \dot+ b) \dot\times c \dot+ (a \dot+ b) \dot\times c' \dot+ (a' \dot+ b) \dot\times c'$ ☆
    と変形して右辺を整理すれば $(a' \dot+ b) \dot\times c = \mathrm{mex}(S')$ と表したときの $S'$ に☆が現れることが分かり同様に矛盾します。

したがって★は正しいです。★の直後の式も $(a, b') \leftrightarrow (a', b)$ となっているだけなのでたぶん正しいです。よって [2] = [3] が成り立ちます。[4] = [5] も同様にして示せます ([2] = [3] と比べて少し易しいです)。


分配法則のほかに結合法則 $(a \dot\times b) \dot\times c = a \dot\times (b \dot\times c)$ も成り立ちます。

CodeChef March Challenge 2019 - Cheating on Queue

Cheating on Queue (リンク)

問題概要

$A_1, A_2, \dots, A_N$ と $K$ が与えられる。
$i = 1, 2, \dots, N$ に対し $B_i := \lfloor A_i/1 \rfloor + \lfloor A_{i + 1}/2 \rfloor + \dots + \lfloor A_N/(N - i + 1) \rfloor$ としたとき $B_i \le K$ となる最小の $i$ を求めよ。
存在しなければ $N + 1$ を出力する。

  • $1 \le N \le 10^5$
  • $1 \le A_i \le 10^5$
  • $1 \le K \le 10^9$

解法

各 $i$ ごとに $B_i$ を求めるのではなく $A_i$ が $B$ に寄与する量を調べるといいです。
更新はだいたい次のようになります。

$B_1 \gets B_1 + \lfloor A_i/i \rfloor$
$B_2 \gets B_2 + \lfloor A_i/(i - 1) \rfloor$
$\vdots$
$B_{i - 1} \gets B_{i - 1} + \lfloor A_i/2 \rfloor$
$B_i \gets B_i + A_i$

もちろんふつうに計算すると $O(N^2)$ かかるのでダメです。
そこで、たとえば $A_i = 22$ として上の更新式の $+ x$ 部分を見てみます。

Bの添字 i-21 ... ... i-1 i
割る数 22 ... 12 11 10 9 8 7 6 5 4 3 2 1
x (商) 1 ... 1 2 2 2 2 3 3 4 5 7 11 22

この表から

  • 割る数が小さいうちはふつうに $x$ を足す
  • 大きくなると共通の $x$ が現れる範囲にまとめて足す
    • 実際は、範囲の左端に $+x$ して右端に $-x$ しておいてあとで累積和をとります

とすればよさそうと分かります。
割る数を $j$ とおきます。「$j$ の小さいうち」は具体的には $j^2 \le A_i$ 程度にすればいいです。つまり $j \le \lfloor \sqrt{A_i} \rfloor$ です。
また $\lfloor A_i/j \rfloor = x$ となる $j$ の範囲は $(\lfloor A_i / (x + 1) \rfloor, \lfloor A_i / x \rfloor]$ なので添字に変換して $B$ の対応する範囲に $x$ をまとめて足しましょう。
計算量は $O(N \sqrt{\max{A_i}})$ です。

提出

https://www.codechef.com/viewsolution/24247755

参考

https://discuss.codechef.com/t/chonq-editorial/22230

NimK (index-K Nim) の必勝判定・必勝側の具体的な手の選択

  • NimKの必勝判定
  • 必勝側の具体的な手の選択

について書きます。
後者は前者の証明に出てくるのですが念のために?指す手を求めるプログラムを書きました。

必勝判定

NimK または index-K Nim とは通常の $N$ 山 Nim の変形で、各手番では山を $K$ 個まで選択して石をとることができるゲームです。それぞれの山に積まれている石の個数を $A_1, A_2, \dots, A_N$ 個とします。このゲームでは $A_i$ を $2$ 進表示したとき桁ごとにとった和について

  • 和が $K+1$ の倍数でない桁があれば先手必勝
  • すべて $K+1$ の倍数ならば後手必勝

が成り立ちます。
たとえば $N = 5, K = 3$ で石の個数が $(22, 11, 42, 23, 19)$ の局面を考えます。$2$ 進表示して各桁の和を $\mathrm{mod}\ K+1$ で求めると次のようになるためこの局面は先手必勝です。

010110
001011
101010
010111
010011
------
132113

証明: 次を示せばいいです。

  • 先手必勝 → 後手必勝の手が存在する

  • 後手必勝 → 後手必勝の手が存在しない (先手必勝に移る手しかない)

【$\exists$ 先手必勝→後手必勝】
$(A_1, \dots, A_N)$ が先手必勝だとします。また $(A_1, \dots, A_N)$ に対し $2^i$ に対応する桁について $\mathrm{mod}\ K+1$ で和をとったものを $S_i$ と書きます。上の例の場合 $(S_0, S_1, \dots, S_5) = (3, 1, 1, 2, 3, 1)$ です。
$S_i$ が $0$ でない最大の $i$ を $t$ とします。つまり $0 < S_t \le K$ であり $t < t'$ については $S_{t'} = 0$ です。$A_1, \dots, A_N$ のうちで $2^t$ に対応する桁が $1$ になっているものが $S_t$ 個あるので、それらを操作対象の山として選択します。選んだ山すべてから石を $2^t$ 個ずつとります。これは石の個数を $2$ 進表示したときに $2^t$ の桁を $1 \to 0$ とすることに対応しています。
ここまでで $S_t = 0$ にすることができました。さらにそれぞれの石の個数について $2^{t-1}, \dots, 2^0$ の桁を $1$ にします。このとき増える石の個数は最大でも $2^t-1$ なのでこの操作は許されます。
上の例では $t = 5$ で $42 = (101010)_2 \to (001010)_2 \to (011111)_2$ となります。
次に $S_{t-1}$ を見ます。$S_{t-1} = 0$ ならば文句なしですが、そうでない場合でも $S_{t-1} \le $ さっき選んだ山の個数 であれば問題ありません。実際、選んだ山に残っている石の個数について $2^{t-1}$ の桁を $1 \to 0$ にすることを $S_{t-1}$ 回行えばいいです。$S_{t-1} > $ さっき選んだ山の個数 であればしかたがないので必要な分だけ操作対象の山を増やすほかありません。新しく操作対象に追加した山について、石の個数を以前のステップと同じように変化させます。つまり $2^{t-1}$ の桁を $1 \to 0$ にしてそれより下位の桁をすべて $1$ にします。$42 \to 31$ としたあとは $S_4 = 0$ となるためやることはありません。
$S_{t - 1} = 0$ にできたので、次は $S_{t - 2}$ を見て...を $S_0$ まで繰り返せばすべての $S_i$ を $0$ にできるため、後手必勝の局面に移れます。たとえば $S_3 = 2$ なので $11 \to (001011)_2 \to (000011)_2 \to (000111)_2$ とします。
ここで気になるのは $K$ 個より多くの山を操作対象として選んでしまうのではないかという点です。しかしその心配はありません。実際、これまでに $k$ 個の山を選んできていま $2^i$ に対応する桁を見ているとします。$S_i > k$ とすると新しく操作対象に加える山は $S_i - k$ 個で済むため、古いのと合わせて選んだ山の個数は $S_i$ 個になりますが $K + 1$ で割った余りを考えているので $S_i \le K$ です。よって選ぶ山の個数はちゃんと $K$ 個以下に収まっています。

【$\not\exists$ 後手必勝→先手必勝】
$(A_1, \dots, A_N)$ が後手必勝だとします。簡単のため先頭から $k$ 個の山 $1, \dots, k$ を選んだとして、それぞれの山から $1$ つ以上石をとり $(A_1', \dots, A_k', A_{k+1}, \dots, A_N)$ になったとします。ただし $k \le K$ です。
各 $A_i'$ には $A_i' < A_i$ より $A_i$ では $1$ だった桁が $0$ になった箇所があります。$2^{r_i}$ に対応する桁がそのような桁のうちで最上位だとします。これより上の桁では $0 \to 1$ になった桁も無いことに注意してください。あったとすれば $A_i' < A_i$ に矛盾するからです。
$2^r := \max_{i}(2^{r_i})$ とおくと $2^r$ に対応する桁が $1 \to 0$ となった $A_i$ の個数は $1$ 以上 $k$ 以下です。一方 $0 \to 1$ となった $A_i$ は存在しません。
$(A_1, \dots, A_N)$ に対し $2^r$ の桁について $\mathrm{mod}\ K + 1$ で和をとった値を $S_r$ として、$(A_1', \dots, A_k', A_{k+1}, \dots, A_N)$ に対するそれを $S_r'$ とします。$(A_1, \dots, A_N)$ は後手必勝だったので $S_r = 0$ であり、$S_r - k \le S_r' \le S_r - 1$ より $S_r'$ は $K+1$ で割り切れません。
したがって後手必勝の局面に移れません。

手の選択

先手必勝局面が与えられたとき、そこから移れる後手必勝局面を上の証明で出てきた手続きによって求めるプログラムです。計算量は $O(N(\mathrm{log}_2(\mathrm{max}A_i))^2)$ です。

#include <algorithm>
#include <bitset>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <vector>

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

void print_vector(vector<int> &a) {
  for (auto e : a) {
    cout << setw(2) << e << " " << bitset<8>(e) << endl;
  }
}

int main() {

  int n = 5, k = 3;
  vector<int> a = {22, 11, 42, 23, 19};
  puts("before:");
  print_vector(a);
  vector<int> x;
  rep(i, 31) {
    int s = 0;
    for (auto e : a) {
      s += e >> i & 1;
    }
    x.push_back(s % (k + 1));
  }
  assert(any_of(x.begin(), x.end(), [](const auto &e) { return e > 0; }));

  vector<int> chosen;
  for (int p = 30; p >= 0; p--) {
    for (auto j : chosen) {
      if (x[p] > 0) {
        a[j] ^= 1 << p;
        x[p]--;
      }
    }
    for (int j = 0; j < n and x[p] > 0; j++) {
      if (a[j] >> p & 1) {
        chosen.push_back(j);
        a[j] ^= 1 << p;
        x[p]--;
        for (int q = p - 1; q >= 0; q--) {
          if (!(a[j] >> q & 1)) {
            a[j] ^= 1 << q;
            x[q] = (x[q] + 1) % (k + 1);
          }
        }
      }
    }
  }

  puts("after:");
  print_vector(a);
  assert(chosen.size() <= k);
  rep(i, 31) {
    int s = 0;
    for (auto e : a) {
      s += e >> i & 1;
    }
    assert(s % (k + 1) == 0);
  }

  return 0;
}

実行すると次のような出力が得られます。
山 $2$ から石を $4$ 個とって山 $3$ から石を $21$ 個とったことが分かります。

before:
22 00010110
11 00001011
42 00101010
23 00010111
19 00010011
after:
22 00010110
 7 00000111
21 00010101
23 00010111
19 00010011

まとめ

NimK では $N$ 個の山に積まれている石の個数を $2$ 進表示して各桁ごとに $\pmod{K + 1}$ で和をとった数を $X$ とすると

  • $X$ (の $2$ 進表示) に $0$ でない桁があれば先手必勝
  • すべての桁が $0$ ならば後手必勝

となります。必勝側のプレイヤーは $X$ の上位桁から見ていき各桁が $0 \pmod{K + 1}$ になるように各山の石を減らしていけばいいです。このとき、すべての桁を $0$ にするために触る山は最大でも $K$ 個で済みます。

参考