ICFPC 2010 参加まとめ
気が付いたら前回の日記がちょうど1年前の ICFPC 参加記だという……。そろそろ日記じゃなくて年記に改めようかと思います(嘘)。
というわけで、今年も ICFPC に参加していました。チーム名は ぴゅあぴゅあこーど++ (pure pure code ++) で、メンバーは @chunjp @gusmachine @izumi_yusuke @nya3jp @phoenixstarhiro @tanakh という、日本競技プログラミング界のエースを集めてきたようなチームでした(自分除く)。
今回の問題はちょっと説明が大変なので、問題文原文かkonnさんによる日本語訳を読んでください、と省略。
今回、基本的に僕はひたすらチームの生産性向上と仕事の自動化に取り組んでいた感じでした。今回のコンテストのレギュレーションだと、大量に市場に出てくる車に対してかたっぱしから燃料を供給する必要があります。そこで我々のチームは、手持ちのソルバで解けるものは自動的に解いて解答を投稿して、解けなかったものに関しては人間が手作業で問題を解析して新しいソルバを作る、という流れを作っていました。僕がやっていたのはまさにこの辺のワークフローの整備と、それに必要なインフラの整備です。今回のコンテストではこのような役割の人間が必要だったんじゃないかと思います。
逆に言うと、ternary encoding の解析であるとか、ソルバのアルゴリズムであるとか、そういったところは（もちろん最低限の sync はチーム内でやりましたが）はっきりと分かっていなかったりします。その辺の解説はきっと他のメンバのみなさんがやってくれると思うので任せます。
ここからは僕の視点からのタイムラインでまとめたいと思います。
19日 0時
やっと帰宅してチームの Skype チャットに参加。問題文の読解と解釈に1時間弱くらい。しかし問題文を読んでも問題が分からなかった。「仕様を推測しろ」多すぎ……。しかもただでさえ論理回路とかは不慣れなのに、3値論理とか言われても困る。
既にチームが論理回路の書式の推測は完了してくれていたので、目下の問題はゲートの真理値表を求めることだったが、これも数時間程度で @phoenixstarhiro さんが決定してくれた。以後こんな感じで何度も若者の人間離れが危惧される事案が発生することになる。
あとはゲートを組み合わせて基礎回路を作ろうということになったけども、この辺で眠くなり脱落。
19日 9時
起きて Skype ログをみたら @tanakh さんが回路ジェネレータを作って219番の車を通していた。さすが。
とりあえず @phoenixstarhiro さんのお宅に向かってチームに合流。一通り sync して、次は燃料の ternary encoding の推測に取りかかることに。
ここらへんで各自がばらばらに燃料を投げて推測していたのだけど、これだと結果の共有が出力を Wiki に貼りつけるくらいのことしかできずいかんなあと思い、Mechanize でサブミットを代行するサーバとコマンドラインインターフェースを作り始めることに。この選択は結果的にとても良かったと思う。
19日 17時
車と燃料の ternary encoding が判明したので、とりあえず手動で解いて解答を投げ始めることに。ternary encoding のエキスパート @phoenixstarhiro さんと @izumi_yusuke さんに手伝ってもらい、Web インターフェースに車を不等式に変換して表示する機能と、行列を入力すると燃料に変換して投稿する機能を追加。@chunjp さんと @tanakh さんはソルバを書き始め、@gusmachine さんは車の作成にとりかかっていた。
はやめに @chunjp さんのブルートフォースソルバが出来たので、しばらくはそれを各自の手元で走らせて、出力の行列を手で Web に貼りつける作業。しばらく6位前後をふらふらしてチーム名をスコアボードに晒して注目を引いたりしていた。
19日 20時40分
Lightning Division があと20分で終了というところで、@tanakh さんが焼きなましソルバを完成させる。「無理ゲーと思っていた問題が運ゲーに変わった」。全員で全力でプログラムを走らせて投稿祭りを開催し、まもなく終了。この時点では5位以上だったみたいだけど、あまり上位ではなさそう。みんなでご飯を食べて帰る。
僕は家に帰ったあと、Web インターフェースをソルバを走らせるサーバとは別のところに引っ越した。実は後にデータ量がふくれあがってCGIがものすごいCPUリソースを食うようになるので、これも正しい判断だった。
20日 13時
ふたたび @phoenixstarhiro さん邸に集まって2日目開始。ここまでは数字の ternary encoding をテーブルで持っていたのだけど、車が増えてきて手持ちのテーブルではパースできないものが出てきたので、再び ternary encoding 班ががんばりエンコーディング規則を一般化。
そろそろ自動ソルバを走らせないとやってられなくなってきたので、適当なシェルスクリプトを組んで自宅サーバでがんがん走らせ始める。
20日 15時
燃料事業に徹してきた我が社が @gusmachine さんの尽力によりついに車事業に進出。以後コンスタントにリリースされていった。
20日 16時
特定の車種を狙い撃ちするソルバが作り始められる。解いているチーム数が少ない車、特にそれを作ったチームしか燃料を供給していない車を解くと、相手の収入源を奪えるのみならず自分にも大きな点が入るので、こういう積み重ねが後々効いてくることになる。この日は手動で他のチームの車を解析してこういうソルバを作成したり、手で提出したりしていたのがほとんどだった。
それにともなってソルバが増えてきたので、仕様を決めてソルバを簡単に追加できるようにした。@chunjp さんも自動ソルバをがんがん走らせ始める。
20日 20時
解いていない車を、他のチームが解いている数や解けやすそうに見えるかどうかで適当にスコアリングして、それに従って自動ソルバにスケジューリングするように変更した。
ほどなく解散。
21日 10時
起きてみたら公式サイトの車一覧にページングが導入されて、スクレイパーが止まっていた……。とりあえず新たに提供された2つのページから車の情報をスクレイプしてくるように変更。更新が終わってみると車が大量に増えていて、CGIを1回呼び出すのに4秒くらいもかかってしまっていたので、キャッシュを付けて対応。
あと、チームロゴを @tanakh さんが作ってくれたのでページに貼るなどした。
この辺の作業を自宅で取り急ぎやってからチームに合流した。
21日 15時
キャパシティいっぱいの車のリリースが完了。
以降は、ひたすら他者の車の解析＆ソルバの作成をしていた。僕は、新たに作ったソルバを適用するために、各車の制約式を grep して狙い撃ち対象を絞るコマンドとかをこつこつと作成してサポート。「すごい勢いで廃車にされていく」「リロードする間にsolvedが50個増えた」など驚きの声が続々と。
21日 18時
自動ソルバがほとんどのケースを勝手に解いてしまうので、人手で解けそうな車を見つけて焼きなましで解答を見つけて提出するまでの間に、自動ソルバが既に解いていた、というケースが頻発。「車はすぐに焼けてしまう」。
21日 21時
終了。最後の数時間は単純作業ばっかりですごく長かった……。
まとめ
とにかく楽しかった！ 最初の ternary encoding 解析とかはプログラミングコンテストじゃなくてパズルゲームじゃないか、という批判もあるようで、確かにそれにも一理あるのですが、とりあえず僕個人としてはそういうのも大好きなので楽しめました（といっても解析はほとんどチームメンバの人がやってくれたんですが……）。他にも、うちのチームはあまり手を回せていませんでしたが、3値論理回路の圧縮とかはチャレンジングで面白いと思います。何より、普段はなかなか一緒に一つの問題にとりかかる機会がないような人たちと、72時間のあいだ一緒にコンテストに参加できるというのはすごく楽しくて、ICFPCの醍醐味だと思います。
サーバが落ちたり、いくつか問題があったのも事実ではありますが、今年の運営の方はかなりの労力を割いてくれたのではないかと思います。感謝です。
さて、気になるのは最終順位ですが、けっこういい線を行っていると予想しています。最終結果が発表されるまで具体的な数値はあまり言わない方が良さそうなのでやめておきますが、各個撃破ソルバのおかげで2チームしか解いていないような車種の大部分をうちのチームが掌握していたので、後で計算してみた periodic revenue は相当な値になっていました。あとは、2日目あたりで既に上位に居たチームにどれだけ追いつけているか、というところです。勝てているといいなあ。
