毎年のお祭り

ということでICFPC 2010に出てました。
去年に続いて(我が家の奥様協力のもと)今年も我が家で。
pure pure code ++ なるチームで、みんなでわいわいやってました。

とゆーわけで、以下体験記＋感想的なもの。
（記憶が頼りなんで、若干時間に前後があるかもだけど、ご愛嬌。）

チームとしては、
パズル(仕様含む)解く、焼きなます、車生産、Tools/Web見たいな分担で、解いてた。
前半は、比較的手作業で仕様/解法を解きほぐす＋自動化の準備をひたすら。
後半は、半自動化されたサーバに、solverをおくと勝手に解いてくれるようになっていたので、あとはsolverを増やす＋改良しまくる。

初日。開始直前。
21:00開始なので、初日はonlineで、翌日朝から集合することに。
「cygwinとか黙殺の方向で」と、いきなり黙殺される。
というわけでVM ware player (Ubuntu 8.02 (劇古))起動。作業はこのなかで。
とりあえず個人的には install まつり。

開始。
しばらくソース管理ツールの使い方で四苦八苦。hg とかろくに使ったことないよ！
で、問題読む。去年より読む速度は格段に上がってたと思う。（英語的な意味で）
去年の教訓を生かして、今年は「specをしっかり書かないことで、specの記述漏れを防ぐ」方法がとられた様子。
1時間くらいして、みんなで読んだところ確認。新幹線からつないでよった者約1名。
ざっくり問題は、
「車をつくって出す + 車に適合した(他チームのもOk)燃料を作って売る -> 燃料の売り上げが得点です、でも税金かかるよ」
という感じ。specの詳細は教えないから、主催者側のサーバにtry&errorでデータ送って、エラーメッセージから推測すべし。という感じだった。エラーメッセージからどう見てもサーバはHaskell製(tanakhさん談)
というわけで、まずはIOを探す。どう見ても(ハードウェアな)回路。ラッチとか超なつかしい。trit(bitの0,1,2三つ状態もつ版) 2-in-2-out。
最初spec読み違えて混乱してたけど、誤解が解けたあとは調べるのは単調作業。IO表を全部埋める。あと、無駄に可視化ツール作成。
最初絵を書いてたけど、慣れてくると暗号みたいな文字列をソラでかけるようになった(ぉ
埋めたあとは、小さいcomponent作成。みんなで、ID/NEG/Const 0,1,2を作成。あとは寝ておきたら好き勝手な出力生成回路を作るプログラムができてた（tanakhさんが一ばｎ(ry）。
ココまでで開始8時間くらい。とりあえず寝る事に。

2日目。
我が家集合。Lightning divisionがあるので、9時集合。おきたら8:30。やべー！
集合したあとは、とりあえず小さいデータから車と燃料の仕様を探す。
Haskell install 祭り。
とりあえず短いほうから総当りしてエラーを見てると、数字の0-10+くらいまで作れるように。
nyaさんの作ったcommand lineからsubmitするツールとかが大活躍。
なんとなく法則があるっぽいけど、とりあえずTableで実装。適当にやってたら、なぜか1問とける。
四苦八苦してると、なんとなくリストの長さを表すEncodeと、数値を表すEncodeがちがうっぽい。
とりあえずよくわからないけどTableで実装。でかい数字はあきらめる。
どうやら一度人間をやめると、なぜかtrit列が数字に見えてそのうち車とか燃料に見えるらしい。
というわけで、ぼちぼち解読して、Encoder/Decoderを分担して作成。加えてizumiさんが比較的でかい数値までのテーブルを準備してくれる。とりあえず解く準備は完了。

なんとなく制約式つきの行列らしいと判明。とはいえ、1x1で解けるものをひたすら実験する。
ぼちぼち車が出てくる。なんかよく見ると手で解けそうな問題がちらほらあったので、解いて見る -> うまくいく。どうやらあってるっぽい。
この辺で、tanakhさんが焼きなまし始めて、ぼちぼち解け始める。
tanakhさん「無理ゲーが運ゲーに」
lightning division終了。

いったん解散。

解散したあとは、ゴルフってみる。
無駄な回路がちこちこあって、簡単に削れるところがぼちぼちあった。サイズは大体2/3くらいに。
他の人のtwitterとか見てると相当無駄があったっぽいけど、結局これがほぼ最後まで生き延びた感じ。
Haskell読めるけど、どうかいていいのかよくわからんなぁ。。。もうちょっと復習が必要そう。

nyaさんサーバのdomain変更。
いくつかの車が読めない問題発生 -> 数が大きすぎる。もうちょいなんかあるよなぁ、と思いつつよくわからず。
Scoring serverにあったbugが直されて、突然scoreがでかくなる。
golfするも、あまり成果は出ないまま。就寝。

3日目。
再び寝坊（ぉ
もう1日あることを考えて、昼前集合。
とはいえ、朝からonlineでごにょごにょ作業はすすむ。
このころには、目で見て解ける問題がいくつもでてきたので、解いていく。
nyaさんサーバ活躍しまくり。あと、燃料のエンコードがそらでできるようになっていた。なれって恐ろしい。
ぱっと見解けない問題は、焼きなまし＋tanakhさん&chunさん最適化コンビによって着々と解けるようになっていく。

すごくでかい数があれば手で解けそうな問題がでてくる。
ということで、trit列とにらめっこ -> 見えたっ（キリッ
で、法則を発見。実装。いくつか手で解く。
数が多くなってきたので、pythonでsolverを実装 -> serversが勝手に解いてくれるようになる。

一方でGUSさんが車量産体制に。最終的には超頑丈な車設計工場に。すごす。
でも、結局何やってたか詳しくはしらないので、きっと書くであろう日記に期待。

この辺で、問題を解くスクリプトを並列で走らせ始める。
焼きなましが終わらない -> nyaさん「cygwinだと ulimit -t がきかないわな！！！」 -> 自分「ああーあーあーあーあーーーああああああ」 -> nyaさん「cygwin ばくはつしろーーーー」 -> while true; do kill -KILL `ps | grep ${プログラム名} | head -1 | awk '{ print $1; }'`; sleep 30; done -> 解決！、、、してないけどいいことに。
CPU稼働率が80%以上を維持。これなんてベンチマーク。。。
tanakhさん、コラ画像作成。webサーバ上に常に表示され続ける。

夜tanakhさんchunさん宿泊。

この深夜くらいから、すごく無理そうな問題も、焼きなましが高次元でさくさく解き始める。tanakhさん神。
だんだん解けるチームが増えてきたのでサーバダウンまつり。
むしろ車の仕様が一時期twitter化。あとで戻ったけど。、、

再びgolf。いまいちうまくいかない。
ちょっと短くなるも、劇的に消す方法は思いつかず。。。きっとshinhさんはすごい短いのを作っていると予想。golf力がたりない。。。

なんか、ぼーっと行列みてたら、

XDAY > XADY

のXとYは同じだからとかって思ってたらぜんぜんだめで、X = [[1 1] [0 0]], Y = [[1 0] [1 0]]見たいな行列だとおもって左肩の数値だけ無理やり比較させる、的な手法を思いつく。手でいくつか解けるように。しかしscaleしない。。。

1問すごく悩むもとけず。就寝。

最終日。
おきたら点数が大変なことに。
tanakhさん「すごい勢いで廃車にされていく」
悩んでた問題が巨大な2素数の素因数分解であることが発覚。無理ゲー。
とりあえずgmpとかにがんばらせる。やっぱり無理ゲー。
これ作ったところはすごい。。。

GUSさん作成、車軍団を公開。
すごく、つよいです。どんだけ寡占かと。
自分たちのsolverにかけて、一度振るったのが結構よかったっぽい。

最後の半日で、golfをやろうと努力するも、報われず。あきらめて、
「機械的には解きづらい、けど人間みたら比較的すぐ解けるようなパターン」を探し出して
pattern match -> 直解放に突っ込む
「どうせ人間がつくってるんだから、解法だってシンプルなはず」探索で、uploadされた車のうち単純なものをかたっぱしから叩き落す。「ヒューリスティック対ヒューリスティック」。
最後の2時間で、数パターンできた。簡単なtemplate見たいになってたので、こぴぺして、式にマッチするパターンと、解法だけ書けば動くようにしといたのは、意外とよかった気がする。

一方でtanakhさん、chunさんペアは、ひたすら焼きなましまくり。というか、とりあえず考え付く手持ちのマシン軍＋数十台のサーバ軍で、焼きなましまくり。「今マシンがアツい！」（我が家もリアルに暑かった。。。

終盤は、最後の車upload祭りに対抗して、燃料投下祭り。次から次へと供給を繰り返す。
と、やってるうちに、終了。
かなり完全燃焼気味。たのしかったーーー。

まとめ

自分的には今回は比較的働けた気がする。少なくとも去年よりは・・・。
最初のほうのパズルと、pythonがりがり書いて簡単な車に燃料投下しまくる足固め的な部分が比較的自分の分野だったっかな。
正規表現を身に着けたのはだいぶ役に立ってたと思われる。あと、Linuxかんきょうを一応用意できたこと。cygwinだったら死んでたな。。。

逆にやっぱり弱いなぁと再認識したのは、数値解法/探索的な分野と、WebService/commandline tool系。
この辺もうちょっと鍛えないとなぁ、、、という感じ。
くわえてgolf力が足りない。。。だいぶ解けてたけど、実装追いつかない部分もあったし。もうちょっとプログラム速く書けるようになりたいなぁ。。。

あと、やっぱり巨大な素数を思いついたチームはすごい。
仕様がはっきりして、どう解けばいいのかわかっても解けない、というのはなかなか。。。

最後に、ここに名言集！が：http://shuns.sblo.jp/article/39084088.html
チームのかたがたへ。楽しかったー。来年もぜひ出よう〜！