🦔

AtCoder Xmas Contest 2019 K: Set of Trees 木の順序を保存する解

2022/09/07に公開

Haskell

3年越しにこの問題を知って今更解いてみたらどの解法とも微妙に異なっていたので記念カキコ．問題はこれ:

やってることは hos.lyric さんや snuke さんの記事で解説された解答と同じく，木に番号を割り付けているだけだが，この番号割り付けが木の順序（順序数としてのGrundy数の順序）を保存するのが多分新しいと思う．

tl; dr

Haskell解:

Rust解:

順序数，つらみ

hos.lyric さんが本問の解説で超限 Grundy 数について解説しているが，これを前提にする．

何をしたいかと言うと，各木のGrundy数 $\alpha_i$ を求めてそのニム和

\alpha_1 \oplus \alpha_2 \oplus \dotsb \oplus \alpha_k

を求めたいのだが，各 $\alpha_i$ は一般には無限も取りうる順序数である．そのようなGrundy数たちのニム和を hos.lyric さんの記事に書いてある式をそのまま読んでとるなら，Cantor標準形を書いた上で順序数の等値性を求められないといけない．Cantor標準形は，各 $\alpha$ を

\alpha = \omega^{\beta_1} + \omega^{\beta_2} + \dotsb + \omega^{\beta_l},\, \beta_1 \ge \beta_2 \ge \dots \ge \beta_l

とか書く，ということなので，結局順序数の順序比較をしないといけないことになる．

Cantor標準形の順序比較は列 $\left(\beta_1, \beta_2,\dotsc,\beta_l\right)$ の辞書式順序なので，最悪の場合「Cantor標準形の式そのもののサイズに比例する時間だけ」かかる．本問の場合，Cantor標準形の形は木の形状そのものなので，二つの部分木に対応する順序数を比較するのに，部分木のサイズの和に比例する時間がかかる．そうなるとふつうに $O(N^2\log N)$ あたりが見えてくる．辛そうである．無理ではなかろうか？

本当に無理だろうか？

「順序保存ハッシュ」，あるいは「背の順位」

アイデア

普通に考えて，大小比較のたびにCantor標準形の深く深く，木の深く深くまで再帰で分け入っていくのは無駄である．もっと楽に比較ができるようにしたい．そもそも，「超限順序数」だの $\omega$ だのと宣いはするものの，でてくる木の同型類の数もそれに対応するGrundy数の総数も結局有限なのだから，もう整数でいいじゃないか．問題になる木，順序数に，小さい順に番号をつけて，それを比較すれば良いのではなかろうか．

したいことは次の通りだ．集合 $S$ を「入力中のある頂点以下の部分木に対応するGrundy数全体」として定め， $S$ の各要素にその大きさを表示する整数を順序を保って対応づける．「順序を狭義に保存するハッシュ」みたいなものだ．だが，この番号は「ハッシュ」という名前に全くふさわしくない^[1]ので，適当に「背の順番号」，いやもっと短く，「背の順位」 と呼ぶことにする．

さて，各頂点に対してはこの背の順位を記録することにすれば，任意の2頂点の比較が定数時間でできる．あとは，この背の順位を求めて各頂点に記録するアルゴリズムがあれば，なんとかなりそうだ．

具体例

それには，単純に木の葉の方から順に背の順位をつけていけば良い．例えば，こんな木があったとする：

頂点0
- 頂点1: 頂点0の子
- 頂点2: 頂点0の子
  - 頂点3: 頂点2の子
- 頂点4: 頂点0の子
  - 頂点5: 頂点4の子
  - 頂点6: 頂点4の子

すると，まず葉に背の順位0がつく:

頂点0: ?
- 頂点1: 0
- 頂点2: ?
  - 頂点3: 0
- 頂点4: ?
  - 頂点5: 0
  - 頂点6: 0

頂点2と頂点4の子は既に背の順位がついている．これらを(大きい順に)列にする．

頂点0: ?
- 頂点1: 0
- 頂点2: ? - $(0)$
  - 頂点3: 0
- 頂点4: ? - $(0,0)$
  - 頂点5: 0
  - 頂点6: 0

ここで，Cantor標準形

\alpha = \omega^{\beta_1} + \omega^{\beta_2} + \dotsb + \omega^{\beta_l},\, \beta_1 \ge \beta_2 \ge \dots \ge \beta_l

同士を比較するとき，列 $(\beta_1, \beta_2, \dotsc, \beta_l)$ 同士の辞書式順序での比較をすることになる，と言うことを思い出す．だから，頂点2と4のうち，より小さい背の順位が与えられるべきなのは，対応する列が小さい頂点2の方だ．そのようにする:

頂点0: ?
- 頂点1: 0
- 頂点2: 1 - $(0)$
  - 頂点3: 0
- 頂点4: ? - $(0,0)$
  - 頂点5: 0
  - 頂点6: 0

まだ番号がついてないもののうち一番小さいのは頂点4だ:

頂点0: ?
- 頂点1: 0
- 頂点2: 1 - $(0)$
  - 頂点3: 0
- 頂点4: 2 - $(0,0)$
  - 頂点5: 0
  - 頂点6: 0

そうすると頂点0に対応する列が決まる:

頂点0: ? - $(2,1,0)$
- 頂点1: 0
- 頂点2: 1 - $(0)$
  - 頂点3: 0
- 頂点4: 2 - $(0,0)$
  - 頂点5: 0
  - 頂点6: 0

列が決まっており，背の順位が決まっていないものの中で最小なものは頂点0なので，頂点0に背の順位をつける：

頂点0: 3 - $(2,1,0)$
- 頂点1: 0
- 頂点2: 1 - $(0)$
  - 頂点3: 0
- 頂点4: 2 - $(0,0)$
  - 頂点5: 0
  - 頂点6: 0

出来上がり．一応だが，葉には空列が対応しており，空列が辞書式順序で最小の列であることを補足しておく．

頂点0: 3 - $(2,1,0)$
- 頂点1: 0 - $()$
- 頂点2: 1 - $(0)$
  - 頂点3: 0 - $()$
- 頂点4: 2 - $(0,0)$
  - 頂点5: 0 - $()$
  - 頂点6: 0 - $()$

疑似コード

これをPython風疑似コードにするとこうなる：

# 入力の整数配列
ps := input()
# 前に適当な数を付け足して1-originにする
ps := [-1] + ps
# n = N+1
n := ps.length()

# 整数列(辞書式順序つき)からなる優先度付きキュー
pqueue := PriorityQueue.empty()
# 各整数列に対応する頂点番号を記録するmap
map := Map.empty()
# 整数配列: 各頂点の部分木に対応する背の順位を記録
refs := [-1] * n
# 各背の順位に対応する順序数をCantor標準形で表示
dict := (empty dynamic array)

# begin with empty sequence
pqueue.push([])

for each vertex i >= 0:
  if iが子（ps[j]=iなるj）を持たない:
    if mapがキー[]を持つ:
      map.update([], map.get([]) + [i])
    else:
      map.push([], [i])

while pqueue is not empty:
  xs := pqueue.pop_min()
  dict.push(xs)
  for each i in map[xs]:
    ref[i] := dict.length() - 1
    if i > 0:
      refchild
        := [ ref[j] for j s.t. ps[j] = ps[i] ]
      if refchildが負の数を持たない:
	refchild.sort()
	  if mapがキーrefchildを持つ:
	    old := map.get(refchild)
            map.update(refchild, old + [i])
          else:
            map.push(refchild, [i])
            pqueue.push(refchild)

さて，これで，任意の2頂点i,jの部分木を比較するには，背の順位 refs[i] と refs[j] を比較すればいいことになった．だからCantor標準形の基底ごとに係数のXORをとることも当然できて，ニム和が取れるようになった．これで解けるはずだ．

本当に解けているのか？

これはTLE解だ

優先度付きキューに列を無遠慮に放り込んでいるが，これが地味に厄介だ．なぜなら列二つの辞書式順序の比較は，列の（小さい方の）サイズに比例した時間がかかる．そのうえ，優先度付きキューは pop_min や push のたびに毎回サイズのlogに比例する回数の比較を実行する．キューに入っている列たちのうちの最長の長さを $L$ , キュー自体のサイズを $M$ として，pop_min や push のたびに $O(L \log M)$ かかるということだ．
だからこの解法も普通に $O(N^2 \log N)$ かかっている．TLE解だ．何らかの改善が必要である．

トカゲの尻尾切り，あるいはsuffixたちへの背の順位の付番

係数付き Cantor 標準形

さて，この節では，ちょっと都合が悪いので Cantor 標準形には退場していただき，係数付き Cantor 標準形:

\alpha = \omega^{\beta_1}m_1 + \omega^{\beta_2}m_2 + \dots + \omega^{\beta_l}m_l

（ただし $\beta_1 > \beta_2 > \dots > \beta_l$ であり， $m_i > 0$ は自然数．）を考えることにする．2つの係数付きCantor標準形同士の大小比較も，列

(\beta_1, m_1, \beta_2, m_2, \dots, \beta_l, m_l)

に関する辞書式順序を考えれば実行できる．

アイデア

さっき背の順位の話をした時と同じ話をする．比較のたびに列の末尾の方まで深く潜っていくのは時間の無駄である．もっと楽に比較ができるようにしたい．辞書式順序で二つの列

(\beta_1, m_1, \beta_2, m_2, \dots, \beta_l, m_l),

(\beta'_1, m'_1, \beta'_2, m'_2, \dots, \beta'_{l'}, m'_{l'})

の比較をしたいというとき， $\beta_1 = \beta'_1, m_1 = m'_1$ だったならば， $\beta_2, \beta'_2$ 以降の比較をしていかなければならない．ところが，もし，

(\beta_2, m_2, \dots, \beta_l, m_l)

(\beta'_2, m'_2, \dots, \beta'_{l'}, m'_{l'})

の背の順位があったらどうだろう？この二つの背の順位を比較すれば良い．すると， $\beta_1$ の比較も背の順位を使った整数の比較でやるなら，比較が定数時間で済んでしまう！結局，

\alpha = \omega^{\beta_1}m_1 + \omega^{\beta_2}m_2 + \dots + \omega^{\beta_l}m_l

の背の順位を考えるときに， $\alpha$ 自身だけでなく，

\begin{align*} \gamma_0 = \omega^{\beta_1}m_1 + \omega^{\beta_2}m_2 + \omega^{\beta_3}m_3 + \dots + \omega^{\beta_l}m_l,&\\ \gamma_1 = \omega^{\beta_2}m_2 + \omega^{\beta_3}m_3 + \dots + \omega^{\beta_l}m_l,&\\ \gamma_2 = \omega^{\beta_3}m_3 + \dots + \omega^{\beta_l}m_l,&\\ \ddots\phantom{\gamma_l=\omega^{\beta_l}m_l+}\vdots\phantom{\omega}&\\ \gamma_{l-1}=\omega^{\beta_l}m_l,&\\ \gamma_l = 0. \end{align*}

という $l+1$ 個の順序数全てに背の順位を与えることにし， $\gamma_{i}$ の背の順位 $\mathrm{ranknum}(\gamma_i)$ は，三つ組

\left(\mathrm{ranknum}(\beta_{i+1}), m_{i+1}, \mathrm{ranknum}(\gamma_{i+1})\right)

の辞書式順序を参照して付番することにする．これを実現するアルゴリズムを作りたい．

具体例

今回も具体例でアルゴリズムを表示したい．

頂点0
- 頂点1: 頂点0の子
  - 頂点2: 頂点1の子
    - 頂点3: 頂点2の子
  - 頂点4: 頂点1の子
  - 頂点5: 頂点1の子
- 頂点6: 頂点0の子
  - 頂点7: 頂点6の子
    - 頂点8: 頂点7の子
  - 頂点9: 頂点6の子

という木を考えよう．今回は，各頂点には最初から $\gamma_l = 0$ （前小節参照）が載っているので， $0$ の背の順位である 0 を各頂点に載せた状態でスタートする:

頂点0: $?0$
- 頂点1: $?0$
  - 頂点2: $?0$
    - 頂点3: $?0$
  - 頂点4: $?0$
  - 頂点5: $?0$
- 頂点6: $?0$
  - 頂点7: $?0$
    - 頂点8: $?0$
  - 頂点9: $?0$

"?" は頂点の部分木全体の背の順位が確定していないことを示す．とりあえず葉の背の順位を確定させる:

頂点0: $?0$
- 頂点1: $?0$
  - 頂点2: $?0$
    - 頂点3: $!0$
  - 頂点4: $!0$
  - 頂点5: $!0$
- 頂点6: $?0$
  - 頂点7: $?0$
    - 頂点8: $!0$
  - 頂点9: $!0$

$!$ は背の順位が確定したことを表す．さて，まずここで， $\omega^0n + 0$ という形の順序数の背の順位を確定させることを考えよう．辞書式順序を考えれば，この形のものが一番小さいからだ．そのために， $!0$ を持っている頂点たちに命令して，自身の親に背の順位 $0$ を報告してもらおう:

頂点0: $?0$
- 頂点1: $?(0,2,0)$
  - 頂点2: $?(0,1,0)$
    - 頂点3: $0$
  - 頂点4: $0$
  - 頂点5: $0$
- 頂点6: $?(0,1,0)$
  - 頂点7: $?(0,1,0)$
    - 頂点8: $0$
  - 頂点9: $0$

葉たちの報告は済んだので， $!$ を外した．つまり， $!$ は，より正確には，「自分の背の順位は確定したが，報告は済んでいない」ことを表す．三つ組 $(0,2,0)$ は，「背の順位0である子2つから報告を受けた．その前に自身が持っていた背の順位は0だった」ということを表す．この三つ組に対して，小さい順に番号をつける． $(0,1,0)$ が $1$ , $(0,2,0)$ が $2$ だ：

頂点0: $?0$
- 頂点1: $?2$
  - 頂点2: $?1$
    - 頂点3: $0$
  - 頂点4: $0$
  - 頂点5: $0$
- 頂点6: $?1$
  - 頂点7: $?1$
    - 頂点8: $0$
  - 頂点9: $0$

頂点2と7は未報告の子を持っていないので，背の順位が正しく確定している．確定マークをつけよう：

頂点0: $?0$
- 頂点1: $?2$
  - 頂点2: $!1$
    - 頂点3: $0$
  - 頂点4: $0$
  - 頂点5: $0$
- 頂点6: $?1$
  - 頂点7: $!1$
    - 頂点8: $0$
  - 頂点9: $0$

$!0$ の報告は済んだので，次に $!1$ に報告させる:

頂点0: $?0$
- 頂点1: $?(1,1,2)$
  - 頂点2: $1$
    - 頂点3: $0$
  - 頂点4: $0$
  - 頂点5: $0$
- 頂点6: $?(1,1,1)$
  - 頂点7: $1$
    - 頂点8: $0$
  - 頂点9: $0$

三つ組の小さい方から背の順位をつける． $0,1,2$ はもう使ってしまったので， $(1,1,1)$ が $3$ で $(1,1,2)$ が $4$ だ：

頂点0: $?0$
- 頂点1: $?4$
  - 頂点2: $1$
    - 頂点3: $0$
  - 頂点4: $0$
  - 頂点5: $0$
- 頂点6: $?3$
  - 頂点7: $1$
    - 頂点8: $0$
  - 頂点9: $0$

頂点1も6も未報告の子を持たないので，確定:

頂点0: $?0$
- 頂点1: $!4$
  - 頂点2: $1$
    - 頂点3: $0$
  - 頂点4: $0$
  - 頂点5: $0$
- 頂点6: $!3$
  - 頂点7: $1$
    - 頂点8: $0$
  - 頂点9: $0$

報告待ちの $!2$ はいないので， $!3$ に報告させる:

頂点0: $?(3,1,0)$
- 頂点1: $!4$
  - 頂点2: $1$
    - 頂点3: $0$
  - 頂点4: $0$
  - 頂点5: $0$
- 頂点6: $3$
  - 頂点7: $1$
    - 頂点8: $0$
  - 頂点9: $0$

まだ使っていない背の順位をつける：

頂点0: $?5$
- 頂点1: $!4$
  - 頂点2: $1$
    - 頂点3: $0$
  - 頂点4: $0$
  - 頂点5: $0$
- 頂点6: $3$
  - 頂点7: $1$
    - 頂点8: $0$
  - 頂点9: $0$

$!4$ の報告：

頂点0: $?(4,1,5)$
- 頂点1: $4$
  - 頂点2: $1$
    - 頂点3: $0$
  - 頂点4: $0$
  - 頂点5: $0$
- 頂点6: $3$
  - 頂点7: $1$
    - 頂点8: $0$
  - 頂点9: $0$

もう一回背の順位をつける:

頂点0: $?6$
- 頂点1: $4$
  - 頂点2: $1$
    - 頂点3: $0$
  - 頂点4: $0$
  - 頂点5: $0$
- 頂点6: $3$
  - 頂点7: $1$
    - 頂点8: $0$
  - 頂点9: $0$

頂点0に未報告の子はない．確定．報告すべき親もいないので，これで完成:

頂点0: $6$
- 頂点1: $4$
  - 頂点2: $1$
    - 頂点3: $0$
  - 頂点4: $0$
  - 頂点5: $0$
- 頂点6: $3$
  - 頂点7: $1$
    - 頂点8: $0$
  - 頂点9: $0$

ここまでの道中で，こういう「辞書」ができた：

背の順位	三つ組
0	なし
1	$(0,1,0)$
2	$(0,2,0)$
3	$(1,1,1)$
4	$(1,1,2)$
5	$(3,1,0)$
6	$(4,1,5)$

実装

上の通りに背の順位をつけていく操作は，頂点に $!$ をつける代わりに，頂点たちを（優先度もつかないただの）キュー（待ち行列）に順番に突っ込んでいけば普通に実行できる．キューの先頭から背の順位が同じものを全部とってきて，親に報告させる．報告を受けた親は (報告してきた子の背の順位, 報告した子の数, 報告を受ける前の自分の背の順位) という三つ組を作る．親たちが作った三つ組たちをまとめて配列に突っ込み，ソートする．そうすれば，報告を受けた親たちに，ソート済み配列の中で若い順から新しい背の順位を与えることができるわけだ．親たちに背の順位を与えると同時に，もし未報告の子がいなければ，その親を報告が必要な子としてキューに突っ込む．これで全ての頂点に背の順位がつく．

背の順位と，上で作ったような「辞書」さえあれば，「各木が持つGrundy数の指数付きCantor標準形において，指数を背の順位に置き換えたもの」がごく簡単に計算できる．あとは存分に XOR を取ればニム和が計算できる．この解答の時間計算量は，ソートがボトルネックになって最悪 $O(N \log N)$ になる．

Rust と Haskell でこの方針での解答を書いた．Rust の方は結構頑張ってコメントをつけたので，疑似コードをつけないのを許してほしい：

Haskell解:

Rust解:

最後に

というわけでちょっとした変種でした．なんかこれって「 $\epsilon_0$ 以下の順序数を Cantor 標準形で表示した式がいくつか与えられる．これらの式のサイズの総和が $L$ であるとき，時間計算量 $O(L \log L)$ で構築可能なサイズ $O(L)$ のデータ構造が存在して，このデータ構造の存在下では与えられた順序数の大小関係は定数時間で比較できる」
みたいなことを言っている気がしますが，論文とかあるんでしょうか？

参考記事

問題:

解説記事:

脚注

ここから構成を見ていくように，これから木/順序数につけていく番号は内部構造だけを参照して「切り刻んで混ぜ(hash)」てつくるような番号ではないので，「ハッシュ」という呼び方は全くふさわしくない． ↩︎

tl; dr

順序数，つらみ

「順序保存ハッシュ」，あるいは「背の順位」

アイデア

具体例

疑似コード

これはTLE解だ

トカゲの尻尾切り，あるいはsuffixたちへの背の順位の付番

係数付き Cantor 標準形

アイデア

具体例

実装

最後に

参考記事

Discussion