No Such Blog or Diary

Suffix tree を線形時間で作るアルゴリズム．しかも文字列を先頭から処理できるオンラインアルゴリズムになっている．なぜかその元論文を読んだのでここにメモっておく．

とりあえず，二乗コストで suffix trie をオンラインに作るアルゴリズムがベース．この suffix trie は，各リーフが suffix に対応し，中間ノードは部分文字列に対応する．このアルゴリズムは，空文字列に対応する suffix trie から始め，それを逐次的に更新していくことで文字列全体に対する suffix trie を構成する．１文字追加することに対応する suffix trie の更新は，各ノードに持たせた suffix link を辿って行われる．suffix link は，そのノードの表現する部分文字列から先頭の一文字を取り去った文字列に対応するノードへのリンク（つまりは，suffix を取る操作に対応した状態遷移のこと）．

このベースとなるアルゴリズムは１文字分の更新にtrieの大きさに比例したコストがかかるため，二乗のコストがかかる．

Ukkonen のアルゴリズムのアイデアは，分岐せずに一列につながった suffix trie のノード達をその根元のノード一つで代表させること．実際のところ，ベースアルゴリズムで構成する suffix trie にはこういった一列に並んだだけのノード列が多く現れ，それらの suffix link の更新が非常に無駄だと感じる．

一文字追加する際の更新で少々面倒なのは，一纏めにされたノード達を適宜分割する操作が必要なこと．これ以外はベースと同じで，一纏めになっているノードに対して suffix link を保持していく．この作業は順次大きくなっていく木を下から上に辿るように行うだけなので（横に飛んだりするけれど概ね全部の分岐で上に向かうイメージ），結局のところならし計算量で線形コストになっている．あとは頭のいいインデックスを使っていて，その更新作業中にループが出てくるが，こちらもならしでループ本体が線形回しか呼ばれないので問題ない．そのならし計算量の見積りは，インデックシングに使われている文字列上のポインタ二つが常に大きくなる方向にしか動かないことによる．

まあ，並列化できそうにないね．

入力サイズnに対してO(n^2)な回路生成器ではやはり無理があった．燃料できてるのに送信すると not connected とか文句を言われるものが大量に…　2x2の行列で数字が大きめとかタンクが多いとかいう問題が結構全滅．3x3以上とか答えが分かっても送れない罠．

んで，終了数時間前にもう少し考えたらO(n)で作れる回路があることに気がついたので実装＆再提出．でも時間ギリギリかつ過去の答えを半分くらい消してしまっていたので答えの再計算に時間がかかるわで結局点数に影響なかった気がする．あとは提出自体にも時間がかかるので送られていない答えがそれなりに溜まっていた．残念．

最終的には，4000台弱の車に対してそのちちょうど半分くらいに燃料供給できたらしい．中途半端以外のなにものでもない成績だ…

そういや一人チームってどれくらいあったんだろう？　チーム人数の統計とかアンケートで出ないかなぁ．

あとは並列計算をどれくらい使ったのかとかの情報も興味があるところ．今回のは小型の回路を構成するための探索とか燃料の計算とか簡単に並列計算できそうな気配だったのだけど，参加者で並列処理したのはどれくらいだっただろうか？　つか，準備が間に合えばEC2+Hadoopとかで力技とかやってみたかったなぁ．来年までには準備しておこう．

順位確定： 32位みたい．

score:                  681.366
others' cars solved:    1956
cars submitted:         0

三進数エンコードの意味がやっと理解出来た．ここら辺のエンコード＆デコードはHaskellが楽だなぁ．それにしても下準備に２日もかかるとは情けない．

そして二日間で理解したこと：　ちゃんと寝ないと頭が回らない．考える前にプログラムを書いて動かすと吉．色々と頭を回すと（数学的な構造を探しだすとか）時間の無駄．

さて，次は「問題取得→簡単なら解く→提出する」を自動化するスクリプトでも組むか．

任意の系列を生成する回路を組めるようになったけれど短くできないなぁ．長さnの系列に対して最悪 O(n^2) かかる．

うーん，もう少し使いやすい回路片をランダムないし全探索で探すべきかねぇ．

とりあえず次はternary encodingをどうにかせねば．

回路組みあがったぁ　→　入れ物に詰め込んだぁ　→　配線があふれるので配線し直しぃ　→　詰め込んだらちゃんと納まったぜぇ　→　電源投入ぅ　→　火ぃ吹いたっ！

いや，配線し直した後の回路テストで無事動くことを確認した後に，絶縁処理の徹底をし無かったために詰め込んだらショートしたってオチなのだけど．久々に煙モクモクな場面を見た気がする．配線焼けまくりだったし．

うーん，自分が全部作業するときには意識せずとも気を付けているのだけど，他の人間の作業を眺めている時には注意が働かないみたい．残念，もういちど．

色々なところで同じサイズの子猫がみゃぁみゃぁ鳴いていた気がする．そういう時期だっけ？

水元公園に早朝の花菖蒲を見に＆撮影しに行くかと思って出かけたのだけど子猫二匹に捕まってそいつらを撮り続けていた気がする．とりあえず明るいレンズが無いと薄暗いなかのビデオ撮影は厳しいかもしれないなぁ，NEX-5．そして子猫達には70300Gのレンズが一番興味深いらしかった．STFもSEL1855も反応薄かったのだけどなぜか70300Gの時だけ無茶苦茶寄ってくるという．そして素早いので薄暗い中では被写体ブレして上手く写せなかった…　いくらISO感度を結構高く出来るとはいえやっぱり明るいレンズ必要だわ．