ICFPC 2016: Team 天羽々斬

EDIT 2016/9/22: !!! 最終順位も2位でした !!! やったぜ

 

ICFPC 2016 に出ていました。ランキング凍結時点で2位でした。優勝してるといいな〜、1位は凍結前で我々の3倍だったり1問を除いて全問解いたりしてますが。

 

ぼくは基本的にはアルゴリズムを考えて実装する係でした。この記事では自分のやったことについて書きます。インフラ周りについては @osa_k がきっと何か書いてくれると思います。

EDIT 2016/8/12: @osa_k が書いてくれました。さすが！

osak.hatenablog.jp

問題: http://icfpc2016.blogspot.jp/2016/08/task-description.html

凍結前のランキング: http://2016sv.icfpcontest.org/leaderboard

ソースコード: https://github.com/osak/ICFPC2016

書いたツール

今年は SOUND VOLTEX からツール名を取りました。

rasis

チーム slack 用のコマンドラインインターフェイス。各人が思い思いの口調で喋らせてキャラ崩壊してたのがおもしろかったです。

ちなみにこのツールはコンテスト開始前に @osa_k が slack を立てた時に作りました。準備は大事。

f:id:pepsin-amylase:20160809070122p:plain

 

maxima

汎用ソルバー。facet（折り紙の折れ線で作られる多角形）が何枚重なっているのかやそれらの表裏や接続関係を全探索して正方形に復元できるかをチェックするアルゴリズムです。

コンテスト開始3時間後のお昼ごはんを食べている頃に思いついてチームメイトに言ってみると軒並み「確かに解けそうだけどバグる要素しかない（線分アレンジメント・双対グラフ構成・動的計画法による重なり枚数の列挙・全域木の全列挙・折り紙の復元）」という反応でしたが開始直後でやる気にあふれていたこともあり気合で実装しました。

Lightning が終了してもバグが取りきれず、一眠りしたあとでデバッグがおおまかに完了しましたが、結局折る回数が2回を超えると計算量が爆発してまともに解けませんでした。凸でないケースが解けるという強みがありましたが、それも @yuusti 作の天空の夜明けで解ける範囲であってこのツールは結局得点にほとんど貢献しませんでした。

いくらやる気にあふれていても事前に実装難易度や計算量を見積もっていれば結末はある程度予測できたはずで、今回の反省点になりました。

grace

すでに解いた問題とシルエットが合同（すなわち平行移動・回転・鏡像反転して得られる）な問題を探してきて解くソルバー。回転行列の導出がやや面倒である以外は、solution の生成で mkut が作った gideon が利用できたこともあってサクッと実装できました。

他のチームが古事記の再利用やそれらに少し手を加えただけの合同な問題を出していることが多かったので、少ない労力で高い効果を得ることができ maxima とは対照的な存在となりました。

また、この合同性を用いてまだ解かれていない問題をクラスタリングし、そのクラスターから得られる得点が多い順に我がチームが誇る折り紙職人が解いていくという戦略にも使用され、こちらも高い効果を発揮しました。

f:id:pepsin-amylase:20160809072948p:plain

grace cluster を報告する rasis。

逆羅刹 (@osa_k 作の管理用サーバー) にもクラスタ一覧を見るページを付けてもらい、最終的にはぼくが何もしなくても職人が解くべき問題を探せる状態になっていました。

tsumabuki

@yowa さんチームが出した問題専用のソルバー。

すべての問題をビジュアライズして眺めていた @yuusti が、Team yowa からの問題は合同でなく grace では効率的に処理できないけれどもかなり規則的な生成法で生成されていることを発見しました。

他のチームもあまり解いていなかったこともあり、専用ソルバーを開発することになって書かれたのがこのツールです。終了8時間前くらいから実装を始めましたが、コンテスト終了までにバグを取り切って目標の問題を全部解き切れました。

反省

maxima をすぐに書き始めずに考え続ける精神力と判断力が必要でした。実装しているときは結構楽しかったけどね。

職人用に grace でクラスターを生成するとかすべてのビジュアライズされた問題をまとめて表示して比較・研究するというアイデアを出すなど、問題そのものでなく問題を解きやすくするための考察をできたのはよかった点です。チームに TopCoder 赤い人が2人もいるので問題考察力以外での貢献をすべきだと考えていましたが、無事達成できました。

来年は Unagi が殿堂入りしてくれたら優勝できるんですかね……。

 1位だったときにチームで出前の寿司をとって食べました。この時は楽しかったなあ。