wataの日記

プロコンや研究の話など書くかも

ICFPC 2019 参加記

今年もUnagiチームのいつものメンバーで参戦。今年の問題は二次元グリッド上でロボットを動かして全部の空きマスを塗りつぶすという基礎タスクに、追加仕様でブーストアイテムなどが加わっていくというものだった。暫定順位では1位なので優勝出来ていると良いなあ

↓分裂アイテムを取って3体で塗っている様子↓

  

使用言語をRustに統一

Unagiチームは例年言語を統一せずに全員異なる言語で参加していたせいもあって、得意・不得意が割とはっきりしていて、問題をたくさん解くタイプは得意(複数ソルバで独立に解けるので)、対戦AIは苦手(複数AIで協力ムズイ)、仕様追加も苦手(追加されるたびに全ての言語で同じものを実装する必要が…)という状況だった。

しかし、2017年のpunterが対戦AI+仕様追加で惨敗したのを反省して、去年はソルバ班がchokudai以外Rustに統一され(元々chokudaiがRustに切り替えると言い出したはずだったのだが…)、今年はついにchokudaiがC#を一行も書くことなく、ソルバ班全員がRust統一となった(インフラ班はGoも使っていた)。

↓ iwiwi が chokudai にRust入門サイトを教えている様子 ↓

去年の参加記(http://wata-orz.hatenablog.com/entry/2018/07/26/194842)にある通り、言語統一の利点は非常に大きく、ソルバ1つをパーツに分けて皆で作っていくことで、各自が自分の担当部分を改良すれば全体のスコアが伸びて分業が捗った。Rustに統一する利点としては、速度が十分速い・バグが出にくい・他の人が書いたコードを使い回ししやすい(自然とグローバル変数を使わなくなる&変更されるものにはmutが必要になるので)というのがあると思う。実際、今回も色んなパーツを別々に書いて組み合わせたら一発で動くことが多かった。学習難易度が高いとよく言われるけど、競プロやICFPCのプログラム書く程度なら意外と簡単なので、バラバラの言語で参加してる他のチームもぜひRustに統一してみてはいかがでしょう!

 

 

以下3日間の流れ

一日目

imos & sulume がインフラ担当して、iwi & tos が入力読み込み・manipulator の可視判定・シミュレータなどのライブラリ部分書いてる間に、自分 & chokudaiがソルバのメインロジック部分を書き始めるという分担でスタートした。

全部のマスを塗りつぶすというTSPっぽい問題なので、ちょうどKaggle Santaと研究でTSPを最近やったこともあり、TSPと言ったらk-optだろーと考えるが、直接踏まなくても周囲のマスを塗れるので難しい…

とりあえず貪欲を書いたら当然大量の取りこぼしが発生して最後に回収する感じになったので、盤面をk-meansっぽい感じで区切って区域間をTSP的に良い感じに順序付け、区域の内部を塗り終えたら次の区域に行く、というのを実装してみた。が、区域の境目あたりを塗る部分で無駄な動きが多く、取りこぼして最後に回収するのと大差ない感じだったorz

一方、chokudaiは左手法で周囲を塗り、内側の塗られなかった各連結成分を再帰的に左手法で塗って外側の左手法パスにくっつけるというのを実装し、かなり良い感じだった。この方針でヤバイケースが特になさそう&ブースターの活用や局所改善などやることが多い&せっかくの言語統一ということでこのソルバをメインに決めて改良していくことにした。

ブースターのうち、extend(manipulatorの数を増やす)と、clone(分裂する)は明らかに重要なので対応することにした。左手法の途中でアイテム拾うのが大変なので、iwiがextendを集める部分を書いて、それを左手法ソルバの最初に呼び出し、更にcloneが出来る後半マップでは自分の没ソルバから盤面を区域に分割する部分を持ってきて、各区域を一体が担当するという感じでつなげたら一発で動いてLightningに間に合った。

 二日目

Lightning終了で少し休憩するかと思ったら4時間後からMiningなる別ゲームが開始するという仕様追加が来た。Miningは、「指定した点を含む/含まない・サイズがいくつ・頂点数がいくつ」などの与えられた仕様を満たすマップを生成するタスクに正解出来ると、一つ前のブロックで生成されたマップに対する塗りつぶしスコアに応じてコインを獲得でき、それを使って追加ブースターを購入して最終スコアを伸ばせるというゲームだった。得られるコインが正解チーム数に依存するため明らかにスタートダッシュが重要で、4時間後の開始に間に合わせるデスマが始まった。大きい正方形から始めて含まれてはいけない点から外部に向けてトンネルを掘り、最後に頂点数を調整するという感じのをtosが書いて間に合わせた。殆どのチームは似たような方針でマップを生成していたようだったが、一部全く違う方針の天才チームも居た(https://twitter.com/yosupot/status/1143107274983890944)。

Miningの1ブロック目に間に合ったのは4チームしか居なかったので、大量の報酬コインを得ることが出来た。が、あまりのデスマに殆どのチームが付いて来れなかったため、なんと9時間後に開始を延期&既に得たコインも没収になってしまった (´・ω・`) 9時間後の再開時はchokudai以外疲れ果てて皆寝ていて、慌てて起きたら延期後に完成した自動提出プログラムと延期後にリファクタリングされたマップ生成プログラムが両方バグって2ブロック不正解になりスタートダッシュに失敗したorz が、その後は順調にコインを稼いでいって、おそらく最終的には一番金持ちになっていた。

ソルバの方は、chokudaiが引き続きブースター完全無視左手法ソルバの改良を続け、自分は殆どのマップでcloneを購入出来そうなのでclone部分の最適化をし、iwiが局所改善(塗らない動きを最短路で置き換える)を書いた。cloneは区域に分割するのはやはり境界部分で無駄が発生する&均等に分割するのが難しいので、一体のつもりで生成したアクション列をk等分するという方針に切り替えた。manipulatorは妥協してkの倍数個回収し全員に同じだけ使うことにした。分割後の開始地点への移動分無駄が発生するので、終点の方が近かったら反転させたり、ビットDPで誰がどの区間を担当するかを最適化したりした。

三日目

chokudaiは引き続き左手法を最強にし、iwiが最適な購入計画をナップサックで求める部分を書き、自分はiwiの局所最適化プログラムを引き継いて枝刈り探索による最適化を追加した。最後一時間くらいで上下反転して右手法にするのも試すと良くなるから後でやろうと言っていたことを突如思い出し、急いで実装して実行キューに投げたらバグっており、急いで直して再度投げるなどしていたらキュー消化のため3000CPUとかが投入されたw