ICFPC2016 Team 天羽々斬

ICFPC2016にTeam 天羽々斬として参加しました。チーム名は、直前に観に行ったシン・ゴジラ(名作なのでまだ観てない人はこんなブログ読んでないで今すぐチケットを予約しましょう)で、ゴジラ討伐部隊の1つが「天羽々斬」と呼ばれており、それを聞いた瞬間にシンフォギアだ!!!!となって勢いでチームSlackのドメインをamenohabakiriにしたところ、そのまま流れでチーム名となってしまいました。

f:id:osa_k:20160811023921p:plain

チームメンバーは弊社同期の8人です。8人!多いですね。確か2012年にBoulder Dashやったときも東工大の西8号館にそれくらい集まってた気がしますが、人数が多いとそれはそれでうまく回すのが大変ですね。

ICFPCはチームを組むと作業の分担ができて楽しいのですが、今回も例に漏れず、アルゴリズム班とインフラ班になんとなく分かれるような感じで計画していました。最終的にはインフラ1:アルゴリズム4:手動(!)3みたいな配分になっていました。僕はアルゴリズム力が(比較的)弱い&サーバ周りの作業が好きという理由でインフラをやりました。自分以外の人間が集中的に使うサービスの管理って実際に手を動かさないと勉強できないんだけど、意外とそういう機会ってないんですよね……。

ということで、自分が何をやったのかを中心に、3日間のチームの動きを書いていきます。ちなみに同じチームの id:pepsin-amylase は仕事が速く既に記事を書いているので、合わせて読むと面白いかもしれません。

pepsin-amylase.hatenablog.com

あと提出したコード群。

github.com


0日目

せっかくのチーム戦だし、普段できないサーバの使い方をしてみたいと思ったので、imosさんの記事を参考にして環境を作ることにした。チームメンバーと相談して、結局以下のような方針に決まった。

  • サーバはEC2のr3.8xlargeをスポットインスタンスで使う。1時間あたり$0.4程度が相場のようなので、72時間取っても$30程度。十分安い。
  • ファイルは基本的にサーバ上に置き、各自sshfsでマウントして管理する。imosさんの記事にあるDropBoxはメリットがよく分からないので見送り。
  • 上記の性質上Gitは使えない or 使いにくいため、バージョン管理はしない。定期的にバックアップは取る。 -- マイクロサービス群も特別なデプロイ作業はせず、共有ディレクトリ上から直接実行する。
  • コンパイルと実行は環境を揃えるため、サーバ上で行う(これはあまり徹底されていなかった)。

チーム名が天羽々斬なので、サーバのドメインtsubasa.osak.jpにした。

1日目

開始と同時に公式ブログに飛んで問題文を読む。折り紙を折った後の形が与えられるので、そういう形になるような展開図を構成する問題らしい。えっ、幾何問題なの……。無限精度の有理数ライブラリが必要とされているらしく、ICPCにありがちな誤差ゲーは避けられるものの、多倍長が組み込みの言語かそういうライブラリを持ってないと無理だよなぁという空気になる。GMPを使うかHaskellを使うかみたいな話が出たものの、kawateaが有理数ライブラリを持っていてなんとかなるかもと言っていたので、とりあえず任せることになる。

問題背景のセクションには、大ブッダ像に祝福されたオリガミを供えて庇護を得るだの、古事記にも数々のオリガミが登場するだの、色々とパワーワードが散りばめられている。電通大が主催だし、やっぱりニンジャスレイヤー好きなんだろうなぁ。

1人で黙々とサーバのセットアップをしている間に、他の人々は折り紙の性質について議論をしたり、本物の折り紙を買いに行ったりしていた。開始から2時間くらい経ったところで各人のやっていることをすり合わせるフェーズに入り、いくつかの事実と、いくつかの方針案が出た。

  • 目標となる形がすべて有理数の座標だからと言って、展開図にしたときも有理数の範囲で表現できる座標に収まるの?→折り紙の周は有理数長さでしか分割されないので、必ず有理数の座標が取れる。
  • スコア効率を良くする方法は?→問題サイズによって決まる基準点があり、完全に一致する折り紙を折れたN人でそのうちのN/(N+1)を山分けし、残りの1/(N+1)を完全一致でない人たちが一致度で比例配分する、という採点方式なので、完全一致解以外はほとんど意味がない。近似ソルバ作ってないで厳密解ソルバに全力を注ぐべき。
  • そもそも展開図から折ったときの形って一意に定まるの?→どうやら定まるらしい。今回は重なりの順番は無視していい(物理的に不可能な重なり方であってすらよい)ので、一般の折り紙よりは楽。
  • 凸包を作ってその形に合わせて折っていけばよいのでは?
  • DPっぽく外周になり得る辺をたどって、長さ1の辺を4本復元できたらなんとかなるのでは?

このうちDP解は展開図の復元が無理そうだったので、凸包解をkawateaが書き、その他の人は折り紙の折り方を研究するなり、必要そうなツールを書くなりすることになった。自分はREST APIを使った問題クローラを書いていた。今回は運営側からREST APIが提供されていて、すべてのアクセスはAPI越しでやれ、むしろ人間用のUIをクロールするな、あと1時間に1回しか更新しないから無駄にクロールしてきて負荷かけんな、という今までのICFPCの反省をふんだんに盛り込んだ制約がかかっていて、運営めっちゃ頑張ってるなぁと思った。

クローラを書き終えるころ、yuustiがビジュアライザ書いたんだけど、これWeb UIで見せることできますかと聞いてくる。どんなのを作ったか聞くと、問題ファイルを入力にして、imosさんのJSビジュアライザの関数呼び出し列を吐くようなものだったので、まあ外部プロセス呼び出しでくっつければいいかと思ってSinatraでフロントエンドを書く(この時は多倍長有理数ライブラリをつかっておらず、doubleを超えるような入力が来て破綻したので後でRubyにポートした)。ついでにUserJSを書いて、公式の問題ページからビジュアライザに飛べるようにする。今思えばこの判断は微妙で、とっとと静的な画像を生成して一覧表示しておくべきだった。あと、無駄に1回生成したJSをキャッシュするような機構にもなってたが、プロセスの呼び出しなんてそんな負荷でもないので、ビジュアライザがアップデートされて情報が増えることを考えると、おとなしく毎回生成するべきだった気がする(実際後で何回も問題になった)。

必要最低限のインフラはできたので、次は各人のプログラムをすべての問題に対して実行した結果を残しておき、性能比較ができるようなシステムを作ることにする。とりあえず逆羅刹と名付ける。実行のスケジューリングとかをRubyで書くのは流石にだるかったし、コケたときのログを残すのも面倒なので、JenkinsのParametarized Buildで実行対象のバイナリを指定したら勝手に走らせてくれるようにする、という方針にした。Jenkinsはなんかゴツいイメージなのでカ・ディンギルと名付けた(適当)。

ビジュアライザで古事記(運営が用意した問題は、すべて古事記に記されているらしい)の問題を見て、10番台に1回だけ折った問題が多いことに気付いたkeitakが、1回折り専用のソルバを書いていて、ちょうど逆羅刹の完成と同じくらいだったので試してみる。

f:id:osa_k:20160811143306p:plain f:id:osa_k:20160811143310p:plain

(Problem 11と12)

何回か失敗したものの、ちゃんと走った。実行結果一覧を眺めていたら、これ一括サブミットできるといいよねとkawateaが言い出したので、ボタンを押した瞬間に全サブミットのループが走り、終わるまで返ってこないという闇のエンドポイントを生やす。このあたりで単純なファイルだけではデータの管理が難しくなってきたので、MongoDBを導入する。その後kawateaの凸ソルバも走らせるようにする。ビルドまでJenkins側でやるようにしたら、jenkinsユーザが644の他人のディレクトリに書き込みできなくてちょっと面倒くさいことになったので、パーミッションを777にすることで解決した(sysadの屑)。

yuustiがまたなんか言ってくる。どうやら今度は解答のビジュアライザを書いたらしい。問題ビジュアライザと同じ仕組みが使いまわせるのでそのようにする。今ひとつ役に立つのか分からなかったが、手動でひたすら折り紙を折っては展開し、折り目を見て手作業で座標を計算していた勢(主にhyonhinaとmkut)には便利だったっぽい。

mkutは「ねじり」を理解したとか言って、方眼紙の上でひたすらねじりの入った折り紙の座標計算をしていた。後で聞いたところ、ねじりは大体90度回転させると一致するやつだから問題は普通の折り紙の4倍簡単で、辺をじっと見てうまく繋がりそうなパスを見つければいいだけだみたいな事を言っていた。よくわからない。

f:id:osa_k:20160811143738p:plain f:id:osa_k:20160811143820p:plain

(Problem 19と98)

この辺で手作業で解かれた問題が溜まってきて、とはいえ運営の用意したフォームで提出するとログが残らなくて不便なので、何かしらログが残る手段で提出したいという自然な需要が生えた。インフラしかやっていなくてもその必要性は十分に感じていたので、即座に提出用のコマンドと、サブミットキューを消化していくデーモン(蒼ノ一閃)を作る。このデーモンが止まると点数が取れなくてやばいので、 id:pepsin-amylase が作ったコマンド(レイシス)でチームSlackに死亡通知を流すようにしたところ、文章が面白かったらしくなんかウケた。

f:id:osa_k:20160811041416p:plain

開始から24時間までがLightning Roundで、この時点での1位は別に表彰されるので結構頑張っていたのだが、3位~4位をうろうろしている上、凸包解法ではそれ以上伸ばせそうになく、半ば諦めていた。するとkawateaが突然、手で座標入力したら折れる気がすると言い出してツールを書き、ビジュアライザで表示した頂点の座標を見ながら簡単な問題を手動で解き始めた。やばい。しかし奮闘むなしく、4位(だっけ?)に留まってしまう。

24時間を過ぎたところからは各チームの問題提出が始まる。解答ファイルをアップロードすると運営側で自動的に折られて問題が作られるようになっており、(5000-解答ファイルのバイト数)/(厳密解で解いた人数+1)の点が入る。解いた側の基準点は解答ファイルのバイト数になるため、2500バイト以内であれば提出するだけ得となる。とりあえず古事記にあった、Fの形をした折り紙をhyonhinaが手作業で解いており(やばい)、他のチームも解いていないようなので、こいつをmkutのGideon(解答ファイルを食わせてコマンドを指定すると、平行移動・回転・任意の直線で折り返しした解答ファイルを吐くやつ)でちょっと回転させたものを提出することにして、家に帰って寝た(ここで朝10時くらい)。

f:id:osa_k:20160811144015p:plain

(Problem32 「F」)

2日目

16時くらいに目覚めて会場に向かう。どうやらcronで仕掛けておいたクローラが寝ている間にうまく動いておらず、問題の更新が滞っていたらしい。cronは難しすぎてよく分からないので、クローラもJenkinsで回すことにする。最初からそうするべきだった……。

kawateaが完全に手折り職人と化してしまったので、折り紙ヘルパーを作ることになる。折り途中の折り紙から折りたい辺と面を指定するとその通りに折れるというもので、例によってバックエンドで動くステートレスなC++プログラムをSinatraが叩いてユーザに送り返すというシステムになった。

https://raw.githubusercontent.com/osak/ICFPC2016/master/images/gekirin.png

これを得たkawateaがものすごい勢いで折り紙を折り始め、簡単だけど手入力は厳しいような問題を次々と人力で解いていってしまった。AIなんていらんかったんや……。手動で解いていたhyonhinaとcarbon_twelveも謎の才能に目覚め始め、特にhyonhinaが、未知の折り紙を勘でどんどん実際に折っていっては展開して座標計算してSubmitという行為を繰り返しており、まさに若者の人間離れだと思った。

f:id:osa_k:20160811145728p:plain

(Problem18 「パカ」(yuusti命名) 現実には内側を開いて潰すように折る操作(潰し折り)が必要になるが、今回の問題では過程は無視して展開図さえ作れれば受理されるため、直線で折り返すだけで作れる(途中で面が切れてもう一度くっつく))

その間に id:pepsin-amylaseグレイスを作って平行移動、回転、鏡像反転で同じ問題になるものを使いまわせるようにしたり、yuustiが天空の夜明けを作って非凸の折り紙を1回だけどこかで展開し、凸にした上でkawateaの凸ソルバに食わせ、最後にmkutのGideonで元の線で折るというパイプラインによる解法を開発し、100問くらい解いた(らしい)。Gideonは元々、古事記の難しい問題をもう1回折ればめちゃくちゃ難しくなるだろうし、回転させると適当な合同判定ルーチンしか持ってないチームには解かれないだろう、という発想の出題用ツールだったのだが、問題を解くためのパイプラインになったのは面白い。この方針でもっと解けばよかった気がする。

そんなことをしていたら、なんとUnagiを抜いて1位になった。魔剤?

Unagiは潜伏しているのかもしれないけど、他のチームも似たようなもんだし、こんな探索しづらそうな問題で大きく差は付かないだろうと思い、現状維持の方針を取ることにする。結果的にはこれが完全に分水嶺だった。とりあえず、グレイスが合同かつ未解決な問題をクラスタリングして提示してくれるようになったので、逆羅刹にクラスタを見るページを作り、手動勢は大きいクラスタから解いてもらうようにする。あと、このクラスタが解けたら何点取れるかも計算したのだが、なんか出力がおかしいのでとりあえず放置する。

このへんから、DAOを書かずに色々なアプリケーションから勝手気ままにMongoを叩いていた影響で、あちこちのフィールドで型が想定とズレて死に、火消しに奔走する。朝になって集中力が保たなくなってきたので、帰って就寝。たしか13時くらい。

3日目

寝て起きたらまたクローラが止まっていたらしい。どうやら前日に帰る直前に入れた変更が良くなかったらしい。ずっと起きてると無自覚でも思考能力がガタ落ちしているので、変なことしちゃだめですね……。そもそもなんでテストしなかったのか。

点数計算のバグがわかる。Problem IDから自分のベストスコアへのHashだと思ってたオブジェクトが実はArrayだったため、変な数値を計算に使っていた。静的に型の付かない言語はこれだから……(責任転嫁する屑)

夕食に寿司を食べていたら、スコアボードも寿司になっていた。一瞬もう凍結されたのかと思った。

Unagiとギリギリ競っているので、Unagiが解けなさそうな問題を出して差を広げようという話になる。とりあえずUnagiがFの折り紙を解けないとは思えないので、もっと難しい問題を作りたい。Unagiが提出している問題を見ると、そもそも折っていくにしろ開いていくにしろダントツで難しい。そこで、Unagiは古事記くらいは解けるにしても、彼らが自分自身で出している問題は解けないんじゃないかという仮説を立て、同じような問題を作ることにする。が、そもそもUnagiの問題が手動でも解けない。仕方がないので、Unagiの問題を解こうとしながら天ノ逆鱗で試行錯誤している最中にできた、Unagiの問題もどきを提出すればいいのではないかとkeitakが主張し始めたので、そういうのを出してみることにする。Unagiの似非なので穴子と命名される。

f:id:osa_k:20160811145533p:plain

(Problem3937 「穴子」)

穴子を出して様子見していたところで2時になる。と、Unagiが10万点くらいスコアを上げて一気に引き離された。えっまじで。潜伏していたのはいいにしても、戦闘力が想定と全然違うっぽい。やばい。 このままだと2位も危うそうなので、特殊ソルバでもいいからもっと頑張って作ろうということになる。自分が起きてくる前に問題一覧をサーベイした人たちによると、yowaさんの問題がかなり特殊な形式になっているらしく、簡単(簡単とは言っていない)な貪欲で解けるらしい。id:pepsin-amylase が専用のソルバを書き始める。

f:id:osa_k:20160811151742p:plain

(Problem1726 ひとつ角を固定し、その角を通るような直線で扇状に折りたたんだ図形になっている。対角線で折られることがないようなので対角の特定が容易にできて、あとはその角から生えている2辺を特定すればよい。)

スコアボード凍結直前の3時。Unagiが70万点くらい、天羽々斬が20万点くらいと、もう話にならなそうな差が付いている。既存の問題を見てみても、1チームだけが厳密解を提出しているものがザクザク出てくる……。これはどう考えてもUnagiが厳密解ソルバを持っているということなので、今から勝つのは無理っぽいし2位維持をがんばろうということになる。つらい。

インフラはいい加減やることがなくなってきたので、少しmkutと議論をする。与えられたシルエットから面どうしの繋がりを維持しつつ正方形にパッキングしていく問題を考えると、探索として解けるかもしれないらしい。ぱっと見はめちゃくちゃ計算量が大きそうだが、確かに色々な枝刈りが考えられるので、枝刈りのプロがいれば実装できるかもしれない。しかし6時間でバグなく高速なソルバにできる自信はなかったので見送られてしまった。

そうこうしている間にyowaソルバが完成する。数回のデバッグと実行を経た後、yowaさんの問題をすべて解くことに成功する。やったー。

また、Skobochkaというチームが、細長くたたんだ折り紙をS字に曲げたものを大量に出しているのを発見したので、yuustiがソルバを書き始める。正確には最初はめんどくさがっていたのだが、Gideonで折る面と折らない面を区別できるようになったら実装してやると言ってmkutを煽っていたところ、mkutが実際にGideonをアップグレードしてしまったため、ソルバを書く羽目になっていた。かわいそう。 残念なことに、このソルバは終了までに間に合わなかった。

f:id:osa_k:20160811153218p:plain

(Problem3961 「S」)

kawateaとhyonhina、keitak、carbon_twelveがひたすら手動で問題を説き続け、時間が来て試合終了。結局手動解法に偏りすぎてしまったのが少し残念。

反省

成り行き上仕方なかったとはいうものの、1人でインフラを全部回すのは厳しかった。システムを作るところまではまあいいけど、実装に使う技術をちゃんと考えておかないと、だんだん体力が削れていく中でデバッグと保守を行うことになり、少しずつシステムが壊れていく。

チームの戦略としては、ソルバにモジュール性を持たせて、雑ソルバでもいいから量産するべきだった。というかそういう風にしたかったのだが、インフラ開発が忙しすぎて自分ではソルバが書けなかったので、他人を説得してそういう方針に引きずり込むのもちょっと難しいという状況になっていた。チームで反省会をしたときにも話題に出たが、数時間に1回くらい完全に作業を中断し、みんなで状況を共有して次の一手を決めるような会議が必要だと思う(というのをICPCに参加していたときからずっと言っているができておらず、成長していない……)

とはいえ、良いサーバを使ってマイクロサービスを立てまくるのは、サービスの本当に最初期の設計を考えるという点でかなり得るものがあった。人数が少なければ指数的に規模が膨らむことはないので、精神的に余裕があれば割といつでもリファクタリングはできる。ファイルベースの管理からMongoに切り替えるとかね。ただし複雑度は指数的に膨らんでいくので、ある程度長期に使われそうなコードならバグりにくい設計を考えておくべきだと思った。あと既存かつ実績のあるプロダクト(Jenkinsとか)はハマリどころが少ないので神。

また、一般論としてサーバサイドアプリとしては異常な構成であっても、割りきってコードの簡略化やモジュール化を進めるのはかなり有効だった。たとえば、REST APIを叩くときにはRubyのNet::HTTPではなく外部コマンド実行でcurlを叩くようにしたり(楽だから)、stdin / stdoutを介した通信でバックエンドのC++プログラムに面倒な幾何をすべて任せたりすることで、管理しないといけない領域を効果的に狭めることができた。

Gitを使わずにsshfsでみんなのファイルを共有して、かつ即デプロイするような環境を作ったのは一長一短だった。他人の成果物へ即座にアクセスできるのはかなり使いやすい。しかし、誰かが使っているコマンドやサービスを改修しようとすると必ず干渉してしまうという欠点がある。特にSinatraのviewは変更が即座に反映されるので、実装途中の機能がユーザに見えてしまうことがよくあって一瞬ではあるものの混乱を招き、精神的に負担が大きかった。

総括

3日間ずっとめまぐるしくコードを書いていたのは楽しかったです。自分がインフラを作っていると、他の人がインフラを使って成果を出してくれるという体験をこの密度でできるのは、なかなか得難い体験ですね。折り紙という題材を最初に見た時はどうなることかと思いましたが、最初の印象以上に問題もジャッジシステムも完成度が高く、ずっと飽きずに、かつシステム面でフラストレーションが溜まるようなことがなく、遊び続けることができました。

チームの動きとしては、もっと探索して計算機の力を使うようにするべきだった感はあります。なまじ人数が多いというのも考えもので、今回のように人間がある程度能力を発揮できる問題だと、すぐに人海戦術に流れてしまう。4,5人しかいなければ確実に探索の方針を考えていたのではないかと考えると、もっといい戦い方はできたんじゃないかなぁと思います。

来年はうなぎに勝ちたいですね。