石の個数が同じになってはいけないニム (山が 2 つの場合), そのグランディ数
石の個数が同じになってはいけないニムはマヤゲームと呼ばれます。(参考: 『石取りゲームの数学～ゲームと代数の不思議な関係～』)
正確には、マヤゲームとは
- 通常のニムで指せる手のうち、ある $2$ 山の石が同じ個数になる手はダメ
- それ以外は OK
- 指せる手が無くなったプレイヤーの負け
というルールのゲームと考えていいです。*1
たとえば $(1, 2, 3, 6, 8) \to (1, 2, 3, 6, 6)$ は通常のニムでは許される手ですが、マヤゲームでは行えません。
なので、マヤゲームでは局面 $(0, 1, 2, \dots, n - 1)$ を渡された側が負けになります。
この記事では、マヤゲームで山が $2$ つの場合のグランディ数を求めます。
一般に、局面 $P$ のグランディ数 $g(P)$ とは「$P$ から一手で移れる局面のグランディ数に現れない最小の非負整数」のことです。
式で書くと次のようになります。非負整数全体の集合を $\mathbb{N}_0 = \{0, 1, 2, \dots\}$, 局面 $P$ から局面 $P'$ に移れることを $P \to P'$ と書いています。
- $g: $ 局面全体の集合 $\to \mathbb{N}_0$
- $g(P) = \min(\mathbb{N}_0 \setminus \{g(P') \mid P \to P'\})$
- $P \to P'$ となる $P'$ が存在しないとき $g(P) = 0$
いまの場合 $g( (0, 1) ) = g( (1, 0) ) = 0$ です。さすがに括弧がうるさいので $g(0, 1)$ などと書きます。
他の局面のグランディ数も計算してみると
- $g(0, 2) = \min(\mathbb{N}_0 \setminus \{g(0, 1)\}) = \min(\{1, 2, \dots\}) = 1$
- $g(1, 2) = \min(\mathbb{N}_0 \setminus \{g(0, 2), g(1, 0)\}) = \min(\{2, 3, \dots\}) = 2$
となります。
$g(a, b) \ (0 \le a, b \le 5)$ の値を表にしました。
| a ＼ b | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 0 | x | 0 | 1 | 2 | 3 | 4 |
| 1 | 0 | x | 2 | 1 | 4 | 3 |
| 2 | 1 | 2 | x | 0 | 5 | 6 |
| 3 | 2 | 1 | 0 | x | 6 | 5 |
| 4 | 3 | 4 | 5 | 6 | x | 0 |
| 5 | 4 | 3 | 6 | 5 | 0 | x |
この表を眺めると $g(a, b) = g_{\text{nim}}(a, b) - 1 = (a \ \mathrm{xor} \ b) - 1$ *2 が成り立っていることに気づきます。
一般の $a, b \in \mathbb{N}_0$ について $g(a, b) = (a \ \mathrm{xor} b) - 1$ が成り立つことを証明しましょう。
$a < b$ の場合も同様に示せるので、ここでは $a > b$ とします。
- $a = 1, b = 0$ のとき $1 \ \mathrm{xor} \ 0 = 1$ より、確かに成立しています。
$g(a', b) \ (0 \le a' < a, a' \ne b)$ や $g(a, b') \ (0 \le b' < b)$ に対し成立していると仮定します (帰納法の仮定です) 。
$\quad S := \{g(a', b), g(a, b') \mid (a, b) \to (a', b), (a, b')\}$
とおきます。$g(a, b) = \min (\mathbb{N}_0 \setminus S)$ です。また、仮定より
$\quad S = \{(a' \ \mathrm{xor} \ b) - 1, (a \ \mathrm{xor} \ b') - 1 \mid (a, b) \to (a', b), (a, b')\}$
となります。次の 2 つを示せば $(a \ \mathrm{xor} \ b) - 1 = g(a, b)$ となるので証明が終わります。
- $(a \ \mathrm{xor} \ b) - 1 \not\in S$
- $0 \le y < (a \ \mathrm{xor} \ b) - 1$ ならば $y \in S$
(1) より $(a \ \mathrm{xor} \ b) - 1 \in \mathbb{N}_0 \setminus S$ となり、(2) より $y \not\in \mathbb{N}_0 \setminus S$ となるので $\mathrm{min}(\mathbb{N}_0 \setminus S) = (a \ \mathrm{xor} \ b) - 1$ が成り立ちます。
[(1) の証明] $(a \ \mathrm{xor} \ b) - 1 \in S$ と仮定して矛盾を導きます。このとき、次のうち少なくとも一方が成り立ちます。- ある $a' \ (0 \le a' < a, a' \ne b)$ があって $(a \ \mathrm{xor} \ b) - 1 = (a' \ \mathrm{xor} \ b) - 1$ と表せる
- ある $b' \ (0 \le b' < b)$ があって $(a \ \mathrm{xor} \ b) - 1 = (a \ \mathrm{xor} \ b') - 1$ と表せる
ここでは $(a \ \mathrm{xor} \ b) - 1 = (a' \ \mathrm{xor} \ b) - 1$ だとします。両辺に $+1$ をして $\mathrm{xor} \ b$ をすると $a = a'$ となり $a' < a$ に反します。もう一方の場合も同様に矛盾が生じるため、$(a \ \mathrm{xor} \ b) - 1 \not\in S$ です。
[(2) の証明] $y + 1 < a \ \mathrm{xor} \ b = g_{\text{nim}}(a, b)$ よりグランディ数の定義から、次のうち少なくとも一方が成り立ちます。- ある $a' \ (0 \le a' < a)$ があって $y + 1 = a' \ \mathrm{xor} \ b$
- ある $b' \ (0 \le b' < b)$ があって $y + 1 = a \ \mathrm{xor} \ b'$
ここで、$y + 1 \ge 1$ より $a' \ \mathrm{xor} \ b$ や $a \ \mathrm{xor} \ b'$ も $1$ 以上で、特に $0$ でないので $a' \ne b, a \ne b'$ です。したがって $y = (a' \ \mathrm{xor} \ b) - 1$ (または $= (a \ \mathrm{xor} \ b') - 1$) $\in S$ です。
まとめ
マヤゲームの局面 $(a, b)$ におけるグランディ数 $g(a, b)$ は $g(a, b) = (a \ \mathrm{xor} \ b)- 1$
おまけ
山が 2 つの場合のマヤゲームは https://ia7ck.github.io/moving-chess-piece-game で遊べます。??? を選択してください。また、Rook を選ぶとニムのルールで遊べます。
Repository:
ニム和とニム積の分配法則の証明
ニム和とニム積に関して分配法則が成り立ちます。
『石取りゲームの数学～ゲームと代数の不思議な関係～』(佐藤文広) にある証明とまったく同じです。それを補足しながら説明します。
非負整数全体 ($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$ などについては分配法則が成り立っているとします (帰納法の仮定)。
以下の式がすべて等しいです。
$(a \dot+ b) \dot\times c$
$\mathrm{mex}\{(a \dot+ b)' \dot\times c \dot+ (a \dot+ b) \dot\times c' \dot+ (a \dot+ b)' \dot\times c'\}$
$\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'\}$
$\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')\}$
$\mathrm{mex}\{(a \dot\times c)' \dot+ b \dot\times c, a \dot\times c \dot+ (b \dot\times c)'\}$
$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
