ICFPC 2013 参加記

@perokugi,@inu_hir0shi,@zr_4でチーム参加しました。
メンバーの方は何か記事に不備があれば教えてください。

一日目
・開始直後
問題をなんとなく理解。
関数値を評価するコード、関数を生成するコードを書き始める。
関数の生成は、DPで全列挙していく方針。
関数値評価は、なんらかの関数言語とC++の２パターンで実装してみることに。

・昼頃
構文解析と関数生成するコードが割と書きあがる。
この時点でチーム内のプログラムはすべてC++で統一することが決定される。
かつ大でお弁当を買って場所を計算機室から@zr_4宅に移動。

・夕方頃
関数生成と値評価が成功。fold,tfoldの処理はこの時点では実装せず。
train,myproblemsが自動処理できるようになる。
二人の実装が爆速なため、コードを書く余地がなかった。
与えられるsizeと演算子でなくても正答することが判明する。
ヒューリスティック局所改善は難しそう、みたいな会話をする。
正攻法で突き進むことにする。

・21時頃
size10程度までなら正答が得られるようになるが限界が見える。
「foldとif0で枝出来るやろ」と希望的観測を持つ。
tfoldの実体が未だわからない。foldのサブセットっぽいからfoldの実装すればとりあえず動きそう。foldの処理を追加。でかい問題が解けるようになった。

・深夜
全列挙できない場合に上限以上の探索を打ち切るコードでsize30が解ける。式簡約の力。
いけるんじゃね！？みたいな雰囲気になる。

・3時頃
そろそろ回し始めないとlightningまでに５００問解き終わらなそう。
そもそも５００問じゃなくて、１０００問以上あった（絶望）

・5時頃
一台で実行し、落ちた問題をもう一台で救済しつつmyproblemsを解き始める。
fold,if0をねじ込む、探索上限を大きくすることで、大抵救済できた。良い緊迫感。

・7時頃
9時までに全て消化するために探索サイズを小さくして計算機3台で回し始める。

・9時頃
チームメイト二人寝てた。850点ちょいgot。結局200問近く解き残してしまった。

二日目
驚くべきことに（！）、何もしていない。どうしてこうなった。

三日目
・昼頃
自宅に再集合する。枝刈りと高速化について考える。
演算子を文字列ではなく、文字で置き換えることに。
ドモルガン、式展開の同値関数の枝刈りを考える。
ボーナス問題は値として枝刈りできそう、みたいな会話をする。

・夕方
高速化の実装を終える。式の体裁がとてもカオスであるが、割と速くなった。
ボーナス問題を倒しにかかる。
if0 (and e1 1) e2 e3の形をしているっぽい。
e2,e3の組み合わせがevalの値を全てみたしうるかどうかで枝刈り。
@inu_hiroshiが実家に帰る。

・20時頃
@perokugiが値としての枝刈りをクラスタリングとかいって実装する。
計算量むっちゃ落ちた。安定してボーナスsmallが解けそう。

・21時頃
解き残した問題と、ボーナスのsmallを解き始める。

・22時頃
ノーミスでボーナスsmallが解き終わる。残ってた問題も8割方解けた。強い。

・深夜
ボーナスlargeを倒しにかかる。
if0 e1 e2 e3のe2,e3がより多くのevalを被覆するように、e2,e3をヒューリスティックに保持。
上手くいかず。
どうやら、同じ性質をもった関数をたくさん保持してしまってるらしい。
大きいボーナスで全然大きいボーナスが得られない悲しみ。

・6時
「我々は、この7時間、なんの成果も得られませんでしたァ！！」

・7時
絶望しつつボーナスlargeを既存のコードで実行し始める。1/5くらいの確率で正答

・9時
終了。

反省点
lightningを精度が低いまま半端に解いて、得られる得点の上限を削ってしまった。
一度生成した式を保存、同値関数の削除を行うべきだった。

良かった点
チームとして意思疎通が取れていたため、停滞することがなかった（最後の7時間以外）

結果
lightning 850ちょい
本選 1250ちょい

追記
lightningで優勝したらしい