Hatena::ブログ(Diary)

yuizumi’s diary

2013-08-12

ICFPC 2013

今年度は @cocodrips と @buno_y と合計 3 人で参戦した。(記憶が正しければ)人生初の男女混成チームである。

ソースコード -- github.com (08/14) | bitbucket.org (08/13)

08/09

  • [09:00] ハングアウトで @buno_y と初対面。問題を読み始める。
  • [10:30] さすがにハングアウトではつらいということで @buno_y の家に集まることを決意する。
  • [12:00] @yuizumi_y5i が @buno_y の家に到着。電車内で Microsoft Research の論文を読んで概略は理解するが、そのアイデアを活用することはとうとうなかった。
  • [13:00] サイスが 3〜5 程度ならばパターンをハードコードできることに気がつく。tfold の意味を理解して、サイズが 8 とかならばパターンを(ry)。
  • [16:30] 各々が Expression を実装する。双方に一長一短ありそうな感じだったが @yuizumi_y5i の実装を採用することを決める。
  • [21:30] ついに 1 点を獲得する。ちなみにこの 1 点が我々の lighting division における唯一の得点である。
  • [22:00] @cocodrips と連絡がつく。翌日以降の会場確認も兼ねて @cocodrips の家に向かう。
  • [22:30] 無事に合流する。問題の内容とチームの状況を @cocodrips に説明する。
  • [23:00] ある理由により @cocodrips のボルテージが著しく上昇する。
  • [23:45] 解散。@yuizumi_y5i はまさかの終電での帰宅。ちなみにこの日は金曜日である。*1

08/10

  • [??:??] @buno_y が @cocodrips の家に到着。サイズが 4 のためのコードを記述する。後に @yuizumi_y5i によりリファクタリングまでされたが実戦投入はされなかった。
  • [11:00] @yuizumi_y5i が @cocodrips の家に到着。
  • [12:30] 昼食をとる。
  • [17:00] @yuizumi_y5i が(理論上は)サイズに依存しない全探索のコードを書き上げる。もっとも、あとから考えると意味のない構造を作っていたり、メモリをじゃぶじゃぶ消費したりと、かなりの問題作である。
  • [19:45] 夕食の弁当を食べながら全探索のコードを実戦投入する。ようやくまとまった点数が入り始める。
  • [21:00] @buno_y が戦線離脱。
  • [22:30] @cocodrips が mismatch のエラーケースを考慮に入れるためのコードを追加する。
  • [23:00] @yuizumi_y5i が戦線離脱。

08/11

  • [10:00] @yuizumi_y5i が @cocodrips の家に到着。あまりの日差しの強さに、その昔「ところで、今日は日差しがきつくてとても暑い。そのため、日なたをあまり歩きたくない。」という文言の問題を作ったことを思い出す。*2
  • [11:30] @buno_y が @cocodrips の家に到着。
  • [13:00] @buno_y が size の値が大きい問題を小さなプログラムで解けないか試し始める。ある程度は解けるが予想されるロスもそれなりに大きそうである。
  • [14:30] @cocodrips が全探索で行けるぎりぎりの条件を見極めながら少しずつ未解答問題を回収しはじめる。
  • [16:30] Unable to decide equality という謎のエラーを食らう。
  • [18:30] @yuizumi_y5i が焼きなまし法*3に基づくコードを書き上げる。ただし fold/tfold に対応していない。
  • [18:45] 焼きなまし法のコードがそれまでの手法とは比べものにならないほど強力なことがわかる。
  • [20:00] 焼きなまし法のコードが tfold に対応する。fold はまだ。
  • [21:00] 遅い夕食をとる。
  • [21:45] 「おお、涼しい。」しかし、都心は 1 分たりとも 30 ℃を下回らなかったらしい。コンテストの疲れは我々の温度感覚すらも麻痺させていた。
  • [22:00] 焼きなまし法のプログラムをついに実戦投入。300点台前半からの巻き返しが始まる。
  • [22:30] @cocodrips「みんなで監視しましょうよ。」この時点で @buno_y と @yuizumi_y5i の朝帰りが確定する。
  • [23:00] 実戦投入中も焼きなましのプログラムが少しずつ改良される。

08/12

  • [00:00] @yuizumi_y5i が参戦記を書き始める。しかし途中で力尽きる。
  • [00:45] 人力並列化が始まる。MapReduce というよりはただの多重実行といったほうが正しい。
  • [01:15] やたら長いプログラムが生成され受理される。
(lambda (x) (fold x 0 (lambda (y z) (if0 (or (xor 0 (xor z x)) (and 1 x)) (and (or (shl1 x) (and (not 1) (not y))) (or 0 x)) (if0 (and (xor (and (or y (or x (not (if0 0 0 z)))) (xor 1 z)) (shl1 y)) (xor (if0 (shl1 (xor z (and z y))) y 1) z)) (or z (not (not y))) (and z (xor 0 z)))))))
  • [02:00] だんだん徹夜特有の体力勝負的様相を呈し始める。
  • [03:30] @buno_y が焼きなまし法のコードを fold に対応させる。
  • [06:45] @cocodrips がインターンに参加すべく京都に旅立つ。タフすぎる。
  • [07:00] 残りの 2 時間を走り切るため @buno_y の家に移る。
  • [08:00] fold/bonus のない問題の処理が終わる(かなりの正答率だが全部に正答したわけではない)。
  • [09:00] 時間切れ。fold のついた問題は全部を処理しきれず。bonus のついた問題にはとうとう手が回らなかった。

*1:もっとも車内はそれほど混んではいなかった。

*2:某会主催の2007年度夏合宿の Day 3 で Problem G として出題されている。

*3:パラメータの設定が初心者すぎて、焼きなまし法というよりは再出発つきの山登り法に近くなっている。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/yuizumi/20130812/1376320342