Xmas Contest 2019 K: Set of Trees

https://atcoder.jp/contests/xmascon19/tasks/xmascon19_k

問題概要

根付き木の順序を，子を降順に並べたものの辞書順として再帰的に定める．根付き木がいくつかあって， $1$ つ選んで「小さく」するという行動ができる $2$ 人ゲームを考える．初期状態が与えられるので，先手必勝か後手必勝かゲームが無限に続くかを判定せよ．

こたえ

盤面の根付き木を $T_1, \ldots, T_l$ とし， $T_i = \{\!\!\{T_{i,1}, \ldots, T_{i,k_i}\}\!\!\}$ とします．後手が勝つ条件は「任意の根付き木 $X$ について， $T_{i,1}, \ldots, T_{i,k_i}$ のうち $X$ と同型なものの個数を $a_i$ としたとき， $a_1 \operatorname{XOR} \cdots \operatorname{XOR} a_l = 0$ である」です．そうでないときは先手が勝ちます (必ず終わります)．このことを後ほど説明していきます．

実装

根付き木を整数に対応させる単射を用意すればよいです．部分木の頂点数が少ない順あるいは最大深さが小さい順などで頂点を見て，

map := 整数列から整数への連想配列
num := 0
foreach 頂点 u:
  v_1, ..., v_k := u の子
  f(v_1) >= ... >= f(v_k) となるようにソート
  if [f(v_1), ..., f(v_k)] !in map:
    map[[f(v_1), ..., f(v_k)]] := num
    num += 1
  f(u) := map[[f(v_1), ..., f(v_k)]]

というように f(u) を定めていけばよいです．この問題の入力形式なら頂点番号が大きい順でも OK です．時間計算量は，次数 $d$ の頂点で $O(d \log N)$ なので全体で $O(N \log N)$ です．

根付き木に対する適切なハッシュ関数をとってもよいです．こちらなどを参照．

順序数

順序数とそれらの演算が出てきます．ある程度既知として進めるのでちゃんとやるのは他の文献に任せます．演算の定義とかはこれで行きます：

順序数は， $0 = \{\}$ と，何かの successor であるもの $\alpha = \beta \cup \{\beta\}$ と，そうではないもの (limit) $\alpha = \sup \alpha$ に分かれる．
- $= \alpha$ ( $\beta = 0$ のとき)
- $= (\alpha + \gamma) \cup \{\alpha + \gamma\}$ ( $\beta = \gamma \cup \{\gamma\}$ のとき)
- $= \sup \{\alpha + \gamma \mid \gamma \lt \beta\}$ ( $\beta$ が limit のとき)
- $= 0$ ( $\beta = 0$ のとき)
- $= (\alpha \cdot \gamma) + \alpha$ ( $\beta = \gamma \cup \{\gamma\}$ のとき)
- $= \sup \{\alpha \cdot \gamma \mid \gamma \lt \beta\}$ ( $\beta$ が limit のとき)
- $= 1$ ( $\beta = 0$ のとき)
- $= (\alpha + \gamma) \cdot \alpha$ ( $\beta = \gamma \cup \{\gamma\}$ のとき)
- $= \sup \{\alpha^\gamma \mid \gamma \lt \beta\}$ ( $\beta$ が limit のとき)

これらの演算は非可換です．

考察

不偏ゲームなので，Grundy 数を (考えられるなら) 考えたいです．局面 $G$ の Grundy 数 $g(G)$ は， $G$ から $1$ 手で進める局面 $G'$ によっては $g(G')$ と書けないような最小の順序数です．いくつか例をやってみると ( $\{\!\!\{$ , $\}\!\!\}$ を [, ] で書いています) 次のようになります．

g([]) = 0
g([[]]) = 1
g([[], []]) = 2
g([[], [], []]) = 3
g([[[]]]) = ω

[[[]]] からは任意の非負整数に進めるので， $\{0, 1, \ldots\} = \omega$ です．

g([[[]], []]) = ω + 1

任意の自然数あるいは $\omega$ に進めるので， $\{0, 1, \ldots\} \cup \{\omega\} = \omega + 1$ です．

g([[[]], [], []]) = ω + 2
g([[[]], [], [], []]) = ω + 3
g([[[]], [[]]]) = ω・2
g([[[]], [[]], []]) = ω・2 + 1
g([[[], []]]) = ω^2
g([[[], [], []]]) = ω^3
g([[[], [], []], [[], []], [[], []], [], [], [], []]) = ω^3 + ω^2・2 + 4
g([[[[]]]]) = ω^ω

こんな感じになるので，次のことが予想できます：根付き木 $T = \{\!\!\{T_1, \ldots, T_k\}\!\!\}$ ( $T_1 \ge \cdots \ge T_k$ ) に対し $g(T) = \omega^{g(T_1)} + \cdots + \omega^{g(T_k)}$ と定めると， $T \gt T'$ ならば $g(T) \gt g(T')$ であり，また， $g(T) \gt \alpha$ ならば $g(T') = \alpha$ なる $T'$ が存在する．

前半は， $T' = \{\!\!\{T'_1, \ldots, T'_l\}\!\!\}$ ( $T'_1 \ge \cdots \ge T'_l$ ) について $T_1 = T'_1,\, \ldots,\, T_{j-1} = T'_{j-1},\, T_j \gt T'_j$ のときには $\omega^{g(T_j)} \ge \omega^{g(T'_{j'})+1} = \omega^{g(T'_{j'})} \cdot \omega \gt \omega^{g(T'_{j'})} \cdot (l - j + 1) \ge \omega^{g(T'_j)} + \cdots + \omega^{g(T'_l)}$ なことを使うとできます．後半は丁寧にやると面倒なので省略するのですが，有名事実を用いて理解することができます．

すべての順序数 $\alpha$ は $\beta_1 \ge \cdots \ge \beta_k$ を用いて $\alpha = \omega^{\beta_1} + \cdots + \omega^{\beta_k}$ という形で一意に書けます．これは Cantor 標準形と呼ばれています． $\alpha \lt \omega^{\omega^{\omega^{\cdot^{\cdot^{\cdot}}}}}$ ならば $\alpha \gt \beta_j$ なので，再帰的に展開していくことでそのような順序数がちょうど根付き木に対応していて，順序数としての順序がこの問題で定めた順序と一致することがわかります．つまりこの問題は， $\omega^{\omega^{\omega^{\cdot^{\cdot^{\cdot}}}}}$ 未満の順序数を根付き木の形で見せていただけなのでした．

順序数は整列集合なので，何をどうやってもゲームが無限に続くことはありません．よって Sprague–Grundy の定理が適用できて，盤面に根付き木 $T_1, \ldots, T_l$ が並んでいるときの Grundy 数は $g(T_1) \operatorname{XOR} \cdots \operatorname{XOR} g(T_l)$ となります．あとは XOR をどう計算するかだけですが， $\omega = 2^\omega$ なので $g(T_i) = 2^{\omega \cdot g(T_{k_1})} + \cdots + 2^{\omega \cdot g(T_{k_i})}$ となり， $\alpha \gt \beta \implies \omega \cdot \alpha \ge \omega \cdot \beta + \omega$ を用いると，最初に述べたように同型なものたちごとに数えればよいことがわかります．