ICFPC 2016 に参加しました (チーム: モダン焼き フジ)

ICFP Programming Contest にcosさん、qwertyさん、seikichiさんとチーム名「モダン焼き フジ」で参加しました。 チーム名は大学生のころによく行ったモダン焼き屋さんの名前から取りました。

最終結果はまだ公開されていないけど、Leaderboard が凍結された時点では13位でした。

レポジトリ: https://github.com/seikichi/icfpc2016

0日目

去年のICFPCでは、メンバーの環境が Ubuntu, Mac, Cygwin とバラバラだったため、環境ごとに微妙に使えるコンパイラオプションとかライブラリとかが異なって非常に面倒だったので、今回は環境をそろえようということになった。 ということで Ubuntu 16.04 をまずセットアップ。

また、去年は CI 環境をコンテストが始まってから用意していたけど、時間の無駄なので今年は事前に用意することにした。 ということで seikichiさんが Jenkins をセットアップしてくれた。 CI サーバは Google Compute Engine の 1CPU インスタンスを利用した。

Makefile もある程度作りこんだものをこの時点で書いておいた。

1日目

全員で問題文を読む。 大雑把に言うと、折り紙のシルエットとスケルトンが与えられるので、どのように折ったらその形になるのかを答えよという問題だった。 個人的に苦手意識の強い平面幾何の問題であり、さらにどうやって探索したらいいのか全く見当がつかない。 これまで参加したICFPCの中で最大の絶望感を味わった。

とりあえず問題の可視化とスコアリングができないと話にならないので、自分とseikichiさんがビジュアライザを、cosさんとqwertyさんがスコア計算プログラムを作ることになった。

ビジュアライザだけであれば Python とか Ruby とかで書くのが楽そうだが、どうせソルバを作るときに C++ 用の入力関数が必要になるので、コードの再利用性を考えてビジュアライザも C++ で書くことにした。 ビジュアライザを作る過程で、問題のspecにアホみたいに大きい座標が含まれていることがわかった。 したがって多倍長有理数を扱う必要があるので、GMP を使うことにした。 C++用のクラスも用意されていて意外と便利だった。

スコア計算は結構面倒そうだから実装には結構時間がかかりそうだなと思っていたら、cosさんがモンテカルロ法による実装をさっくり作ってしまって凄い(小並感

昼食後、弱くてもいいから何かソルバを作ろうということで、seikichiさんが初期状態から並行移動して重心の位置を合わせるだけのソルバを作った。 一瞬だけランキングで２位になった。

その後、x軸、y軸に並行に何回か折るだけのソルバを作った。 これで単に長方形になるように折っただけの問題は解けるようになった。 また、予め与えておいた角度を全探索することで、既知の角度で回転している長方形は解けるようになった。 問題の制約として、全ての座標が有理数でないといけないという制約があるため、みんな似通った角度で回転させるので、この(頭の悪い)方法でもそこそこ正解したりもした。 また、長方形を適当にスケーリングしてみて resemblance を稼ぐみたいなこともやった。 （この時点では、このコンテストにおいては厳密解のみが正義で近似解に人権はないことに気付いていなかった）

ソルバを動かすのに時間がかかるようになってきたので、GCEで16コアのVMを借りた。

自分が長方形ソルバを作っている間にcosさんがスコア計算を高速化したりライブラリを整備したりしていた。 また、seikichiさんがソルバの性能（解けた問題の数、平均resemblanceなど）を Jenkins でグラフ化してくれるやつを作ったり、問題が増えた時に自動で fetch してきて git レポジトリに push してくれるやつを作ったりしていた。 その裏でqwertyさんが手計算で黙々と提出用の問題を作っていた。

3時ぐらいに寝た。

2日目

起きたら11時だった。 qwertyさんは早起きして問題を作っていた模様。さすがすぎる。

cosさんが任意の直線で紙をfoldする関数を作った。 これでようやく我々のチームも長方形以外の形が折れるようになった。

fold関数を使って凸包ソルバを作った。 サイズ制限にさえ引っかからなければ、シルエットが凸である形は厳密に折れるようになった。 例えば以下の形が折れるようになった。

その後、Twitter をしているとモダン焼き フジに言及している人を見つけた。

ICFP Programming Contest 参加者、意味もなくモダン焼きの CM 見せられている。

— 宇宙ツイッタラーX (@kenkoooo) 2016年8月7日

seikichiさんがすごい勢いで Jenkins のパイプラインを整備していた。 新しい問題が追加されたら自動で既存のソルバ群が実行され最良のスコアが自動で提出される感じのシステムが構築されていた。 その裏でqwertyさんが黙々と提出用の問題を作ったり、兜とか風車とかを手で解いたりしてた。

12時過ぎぐらいに寝た。

3日目

起きたら11時だった。 qwertyさんは早起きして問題を作っていた模様。さすがすぎる。

そろそろ探索を書かないとまずいということで、全探索ソルバを書いた。 最終形から unfold していく方針は unfold 時にどの面とどの面に別れるかがわからないため難しいと判断して、初期状態から直線を適当に選んで fold していく方針にした。

このとき、スケルトンに現れている直線の集合をそのまま探索の候補として使うことはできない。 なぜなら、ある直線にそって紙を折ると、それまでの折り目がその直線によって反射されてしまうので、最終的なスケルトンに現れない場合があるので。 そこで、深さ0ではスケルトンに現れる直線の集合を候補として使い、深さnでは深さn-1の候補集合に加えて最後に選んだ直線で候補集合を反射したものを候補とするようにした。

この全探索はその見た目どおり計算量が凄まじく、実行してすぐに答えが返ってくるのは max_depth=2 までで、max_depth=3 だと10秒以上待たされるし、max_depth=4 だと返ってこない。

また、前から fold していく方針なので、初期状態で紙がどれぐらい回転及び平行移動しているかを求めないといけない。 とりあえず多くの場合で使えそうなヒューリスティックとして、スケルトンに含まれる直線から「同じ点をどちらかの端点に持ち」「互いに直交しており」「直線が水平になるように回転したときに、あらゆる有理数座標が有理数座標に移る」ような２直線を選んできて、その２直線と初期状態の紙の角を合わせるという方針を取った。

全探索ソルバによって、3手以内で折れる問題は解けるようになったが、実際の問題はもうちょっと手数のかかる問題が多い。 例えば、紙を水平方向に3回折って 1/8 の幅の長方形を作った後に1～2回適当に折るみたいな問題がいっぱいある。 ということで、全探索ソルバに初期値を与えることができるようにした。 これで下図のような既知の初期状態（1/8長方形、1/16長方形、1/2三角形など）からちょっとだけ折ったような問題には答えられるようになった。

また、既存の問題を平行移動したり回転したりしただけの問題が大量に存在しているが、これもそのうちのひとつを解けば、初期値付き全探索ソルバが max_depth=0 で答えを見つけてくれるようになった。

その後は seikichi さんが問題一覧を見れるウェブサービスを作ったり、既に正解した問題を自動計算の対象から外したり、念のため全問題再提出などを行ったりしていた。 qwerty さんと cos さんは黙々と手で問題を解いていた。 自分は凸包ソルバや全探索ソルバをちょっと弄って何かできないか試していたが、結局そこから５問しか解けなかった。

まとめ

最終的に 3528 問中 1872 問を解くことができた。 1日目の絶望感からすると結構健闘したような気はする。