Crayfish Scrivener (IOI 2012, day 1)

6月は永続データ構造強化月間（そういうことにしました）、ということで
qnighy先生の
Re永続データ構造が分からない人のためのスライド
で紹介されていた、IOI 2012の"Crayfish Scrivener"を解いてみたメモ。

自分の方針は
・trie木を作る。TypeはO(1)（であってほしい）
・ある時点でどこにいるか、ポインタを配列に入れておく。これでUndo操作はO(1)。
・ある時点で、rootから辿って(P+1)文字目は何か？trie木を今いる方向に辿るとか、簡単そうで簡単じゃない（O(1)では無理的な意味で）。root方向に快速、急行、特急で向かうポインタを各ノードに持たせればいいんだろうとは思うんだけどどうやって計算する？
ってところで。

$(1,2,4,8,\cdots,2^k)$ だと親ノードのそれからの計算が大変かなと思って $(0,1,2,4,7,12,20,\cdots)$ みたいなのを使ってたんだけど、これは $fib(n)-1$ に相当する数列で、親のポインタ $(0,1,2,4,7,12,\cdots)$ は子供から見ると $(1,2,3,5,8,13,\cdots)$ に相当するから、これの2項目から $(2,3,5,8,13,\cdots)$ に $(0,1,2,4,7,\cdots)$ を足したら $(2,4,7,12,20,\cdots)$ になるし楽かな、と。
（いや、 $(1,2,4,8,\cdots,2^k)$ の場合、親(-1)の親(=-2)の2つ上(-4)の4つ上(-8)の、って辿っていくだけだから簡単だし、 $\log_2{10^6}=19.931\cdots$ で高々20要素の加算でrootまでの経路上の任意のノードに到達できるし。これに対し $fib(n)-1$ 方式は隣接項の比率が黄金比に収束するから大体 $\log_\phi{10^6}=28.711\cdots$ で、最大29要素の加算が必要になる（＝1.5倍弱の演算が必要）。