No Such Blog or Diary

今年の実験を見た限りでは制御用のドライバ回路をゼロから組ませるのは大変だなぁと．それでも空飛んだので今年の連中はよくやった．そして発表に編集した動画を持ち出したのも良かったかもしれん．実験の発表なら面白くなければいけない．もう少しテンポよく行けるとよかったけど．

さて，来年の実験のネタは何にするかね．SunSOPTひとつお亡くなりになったけど来年もSunSPOTネタで動くものにするが，はたまたFPGAでリダクションマシン作って遊んでみるか．FPGAの方が工作量が少なくて楽かもしれないが…　派手さに欠けるよなぁ．

とりあえず余ってる部品でそのうち空中に停止するように作り変えるか．あとは適宜重心をとれるような制御と．駆動系のパワー自体も一度測定しておいた方が良いなぁ．

わーお，思ったよりだいぶ多いぜぇ．まあ，普通には交通費か．

充電できないリチウムイオン電池を保護回路バイパスして充電してみた．充電器にも保護回路入っているので問題ないと思うけど，一方でやっぱりちょっと怖かったりする．まあ，本番は明後日なのでそれまでもてば問題ないから良しとしよう．

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が楽だなぁ．それにしても下準備に２日もかかるとは情けない．

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

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