ICFP Programming Contest 2010
きたまさが数学界に引きこもってしまったので今年はid:iwiwiと二人で参加。
チーム名はHITOCry
前回は劣化マラソンな感じで初日で飽きてしまったが、今回はなんか面白かったので完走した。
結果は7位だったorz
作業はGmailチャット+DropBoxのファイル共有で行った。
以下チャットのログから掘り起こした全体の流れ
一日目 21:30
開始前に仮眠をとったら３０分位寝過ごしたorz
一日目 23:00
１時間半くらいかけてようやく問題文を理解し、とりあえず工場のフォーマットを調べるために提出しまくることに。
二日目 01:00
ようやく工場のフォーマットと入力例の最初１７文字が解読された。
次はゲートの解析をすることに。
二日目 02:00
ゲートの入出力表の解析が完了した。
次はkey prefixを作成することに。
3進17文字なので3^17個くらいランダムなの試せば見つかるんじゃね、と思ってランダム生成することにした。
二日目 03:00〜10:00
秋葉さんが寝てしまったのでログがないorz
ランダム生成でkey prefixの生成に成功して得点ゲット。
入力が17文字しか分からないのでどうしたらいいか…
入力に依存せずに決まった出力を出す回路を作るしかないよなーという方針で色々考えることに。
1入力1出力で最初のターンにiを出力し、その後入力をそのまま出力し続ける回路が構築できれば、それ逆順につなげれば任意の列が出力できるという結論に至ったので、この回路を探索することにした。
が、全然見つからないorz
仕方ないのでさらに分割して、
1. rightが0の時i、right=rのとき入力をそのまま出力する回路
2. 入力によらず、rを出力する回路
を組み合わせることにした。
これはランダム生成ですぐに見つかり、ようやく回路自動生成器の作成完了。
しかし、１文字あたりゲート10くらい消費するしょぼさで、他にもやることいっぱいあったので結局こいつを最後まで利用することになったorz
たしかここらへんで8:00くらい
せっかくなのでそのままさらに燃料フォーマット解析に着手。
燃料の最初が[タンク数][成分数]と並んでいることが分かったので、これを利用して小さな数字の列挙を終えたあたりで力尽きて寝た。
二日目 15:30
未だに燃料フォーマットがさっぱり分からないが、別の車で通った燃料を他の車にも投げたら通ったので、とりあえず通った燃料を投げまくることに。
なんかいっぱい通ったｗ
二日目 17:00
未だに燃料フォーマットがわからない…
秋葉さんが自動提出スクリプトを書いて、車リスト更新しながら、それまでに見つかった正しい燃料をひたすら投げ続けるようになった。
二日目 18:00
成分数が1な燃料のフォーマットは解析できたが、成分数が増やせないorz
燃料の解析を諦めて、先に車の解析をすることにした。
二日目 20:00
車のフォーマットの解析が完了。
数字のフォーマットに二種類あるとか予想外すぎた。
この発見により燃料フォーマットの解析もついに完了。
二日目 21:00
ライトニング終了。
トップ10入りならずorz
手動で作った燃料で問題解くことに成功し、次はソルバーを作るかー。
と、その前TopCoderに向けて休憩＆仮眠。
三日目 03:00
TopCoderから復帰。
寝る前に自動ソルバーを作って、動かしながら寝ることに。
とりあえずパーサー書いて食わせたらエラー落ち…
値がでか過ぎて用意してあった数表で足りなかったorz
というわけで数字フォーマットの推定or数表の拡大をすることに。
三日目 04:00〜7:00
秋葉さんが寝てしまったのでログが…
数字のフォーマットはイミフ過ぎて分からなかったので、とりあえず数表を拡大した。
てきとーにランダムソルバーを作って数問解けた
解けないやつ見てたら、なんか超でかい数が必要そうな問題(x>y^n, y^{n+1}>x)だったので、数字のフォーマット推定必須かよ…と思って再び頑張るも分からずorz
秋葉さんが書いた自動提出スクリプトに載せようと思ったが仕様が若干違って、しかも自分Ruby分からなかったので書き直せなかったorz
というわけで自動提出は諦めて寝た
三日目 15:00
起きたら秋葉さんが自動提出動かしてた。
車増えまくりでサーバー大丈夫か心配になってきたｗ
自分が数字フォーマットの推定をし、秋葉さんが車を作ることにした。
三日目 16:00
燃料の方でタンク数大きくすると1000くらいで文字数がたりねーよエラーになり、いくつになったか分からねーと困っていたが、車の方でタンク番号を大きくすればいいことに気づき、数表が拡大。
100万くらいまで作って、いい加減パターン見えないかなーと思うも一向に見えてこない…
3^nごとに謎のprefixがついてその後ろに3進数なのは分かるんだが、このprefix謎すぎる…
とずっと考えていたら、prefixがまた再帰構造になっていることに気づきようやく解決した。
次は成分数1専用ソルバを作ることに。
成分数が1の時は、両辺logとると線形になるので単体法とかで解ける。
三日目 17:30
成分数1ソルバが完成。
一気に大量の車が解けた。
秋葉さんの作った車がこのソルバで解けてしまうことが発覚。
成分数１で解けないようにするために、両辺の変数の出現回数が一緒で並び順が違う不等式を必ず入れることにした。
我々のソルバで解けない車がついに完成し、初出荷！と思ったらなんか謎のエラーが出て出荷できないorz
色々直したがずっとエラー…
三日目 19:00
ソルバーが順調に車を解いている。
車一覧に解けたかどうか表示するプログラム書いて出してみたところ、solved4くらいまでは大体解けてるのに、一部全然解けてない領域が…
どんなのだろうと見てみたら明らかに成分数１で解ける車だった
というわけでソルバのバグ修正に
三日目 20:00
バグ修正完了。
車の方はまだエラー。
なんかでかすぎるぽい。
というわけでサイズ小さくしたらうまく行って初出荷に成功！
wktkしながれ見てたら3分で他のチームにとかれたorz(ちなみにこの車、最終的に解いたのこのチームのみ…)
三日目 21:00
最強の車にするために、solved1な車の分析をすることに。
左辺のサイズが右辺のサイズより小さいのが難しそう、というわけでこういうのを作ることにした。
自分はソルバーの改良することに。
結構な問題が01行列で解けるぽいのでそれ専用ソルバを追加した。
秋葉さんが二台目の車を出荷！
しかし、またソッコーでとかれたorz(この車も最終的に解いたのはこのチームのみ)
三日目 22:00
秋葉さんの車は成分数とか色々変えながら数台出荷するも全て１チームに解かれる…
自分はランダムソルバを局所探索に変更した。
四日目 00:00
どうやらうちらの車を解いているチームは田中さんのとこらしい…ということが発覚し田中さんやべぇを連呼。
もう諦めて出荷しまくるかぁということになり、秋葉さんが車自動出荷スクリプトを書いた。
ソルバの方は局所探索ソルバがそこそこ解いてるぽいが鯖がつながりにくすぎて提出失敗しまくり…
車自動出荷スクリプトが完成して動かしたところ、鯖が重すぎてタイムアウトし、車IDが取得できない…
６台目の車IDが分からなくなってしまったので、急遽中断
四日目 02:00
なんか急に車のサイズ制限が100文字以下に変わった…
我々の車はそんな小さいはずもなく、100文字以下でつくってみたところ自分たちのソルバでよゆーで解けた…
さすがにありえなくね…というわけで寝た
四日目 08:30
起きたら車一覧ページが変わっていて自動提出が死んでいたorz(完全には死んでなくて穴抜けになっていたらしい)
とりあえず手動で全車リストを取得してソルバを回しておいた。
車のありえないサイズ制限は解除されていた。
授業があるので大学へ。
四日目 10:15
秋葉さんが自動提出スクリプトの修正を行い、自分は手動で問題選んで解いてた。
車ごとの燃料サイズ一覧が公開されており、我々の回路が超でかいことが明らかに…
しかし今更作りなおしている時間などないorz
昨日出した車は未だにsolved2だったが、敵チームの方が回路が小さくて我々には1/3点しか入ってこないorz
やはり頑張って解かれない車をつくるべきという結論に。
四日目 12:00
ファイル同期ミスとかでデータがぶっ壊れていたことが発覚。
秋葉さんが頑張って直しつつ、車をいろいろと出荷。
四日目 13:00
時間もないので一気にまとめて２０台出荷した。
四日目 14:30
1時間たってもまだsolved1 ktkr
というわけで大量出荷開始。
72台出荷完了した。
四日目 16:00
ソルバを焼きなましてみたりしたが一向にムズイ問題解ける気配がないorz
車は40台ちょいがまだ生き残っていた。
点数が蓄積型なのでもはや大逆転は無理だなーと思いつつもベスト５位までいけないかなーと頑張る。
四日目 19:30
7位まで上がった。
もはやなにしても順位変わらないだろうということで、秋葉さんと晩飯食いに行って試合終了。
終了
結局７位だった。
解いた問題数は2424/3784
生き残った車は5/71,1チームのみに解かれたのが61/71 (1台行方不明)
どう考えてもぴゅあぴゅあがうちらの車解きまくったのが敗因ですね
これはもう責任とって優勝してもらうしかないｗ
