ICFPC2019

職場の同僚に誘われて初参加。"Gon the Fox"の一員でした。面白かったので覚えてるうちに自分がやったことの記録や感想を書きなぐっておく次第。

day1

職場のエンジニアメインのチームなので、終業後のオフィスを占領して参加。問題が公開されてとりあえず読む。ソルバー班とインフラ班に分かれようという事になり、インフラ系の知識が皆無な自分はソルバー班に。

問題は「2次元グリッドで表される地形をロボットで巡って全部塗ってね。アイテム使って塗る面積を広げたり、ロボットの数を増やしたりもできるよ」という感じだった。

最初のお仕事はInputの構文解析。探索領域が (0,0),(1,0),(1,1),(0,1) みたいな文字列として渡されてたり、使えるアイテムも B(2,3) という感じで文字列で与えられるので、これを慣れ親しんだ競プロっぽい形式(W×Hの文字でフィールドを表したりする)に直すコンバータを書くことに。

とりあえず皆でやって最初に動いたやつを使おうという事になり、とりあえず書いたらなんか動いたのでそれを使ってもらえることになった。この辺で周囲の飲食店が閉まりそうな時間になってきたので夕食(夜食?)へ。

その後はしばらくソルバーを書いていた。まずはアイテムを使わずにという事で適当な貪欲を書いたりしていた。Lightning Sectionの終了ちょっと前に用事で抜けなければならなかったので、始発で一時帰宅。ついでに仮眠を取った。Slackの通知で目を覚ますとロボットを増やすアイテムが追加されたとか激ヤバな事が書いてあったので急いでオフィスへと戻った。80/300ケースという事だったので、自分はひたすら1人用の最適化に勤しんでいたが、用事で抜けるちょっと前に微妙にステップ数を減らすのに成功しただけだった。つらい…。

day2

用事を終えて戻れたのは、まもなく日付が変わって日曜になろうかという頃。Ful Contestの仕様はとっくに発表された後で、Slackがざわざわしていたので早く戻らねば…と思っていたが電車を間違える痛恨のミスにより帰還が30分くらい遅れた。ちなみに帰還は最初に設定されていた締切である23時よりも後だった。ビッグウェーブに乗り遅れた感が悲しい。

19時に「23時から15分おきにマイニング用の問題だすで。出された問題の解と、別に与えた仕様を満たす問題をセットで送るんやで」という仕様が発表され、デスマ不可避だったらしい。問題解くのは既存のソルバーの中で一番良い解を返しておけば当面良さそうで、パズルジェネレータの用意が急務のようだった。自分が手をつけようかという頃にはマイニング開始が翌9時からに延期されていたので、電車間違う程度の疲労度を加味して一度仮眠を取る事にした。

自分のジェネレータの方針はこんな感じ

• 含むべき点にフィールド周囲4辺の中点らへんを足しておく(サイズ制約用)
• 含むべき点をSelf-Intersectionが出来ないよう注意しながらプリム法っぽく結ぶ
• 今の領域に隣接するマスについて削った時の外周の頂点数の差分を計算しておき、(最低頂点数)と(最大頂点数)の中間値を目指すようにマスを選んで、最低の面積を満たすまで領域を広げていく

納期の9時を過ぎること1時間(申し訳ねぇ…)、こんな感じのマップが作れるように

Generator

多少制約でいじわるされても良いように頑張るぞ(๑•̀ㅂ•́)و✧ という気持ちで書いたが、他のチームのマップを見ていたら頑張り過ぎた感も否めない。完成が遅れてマイニングを3回くらい落としたのが激痛だったが、完成後は一度もマップ生成に失敗する事はなかったし、3回くらい問題が採用もされたのでまぁ良いかということに。

day3

複製はマラソンガチ勢のチームメンバーが対応済でレッドオーシャンだったので、テレポートの対応を試みていた。が、4時間くらいかけて全く良くならず最終的にはテレポート対応のコードを全部消した。実装力が足りなかったのか、見切りをつけるのがおそかったのか、どちらにしても対応が悔やまれる部分だった。

day3あたりにしてついにマイニングで稼いだお金はアイテムに換金した方がお得っぽい、という話になった(しばらくアイテム購入に関しては懐疑的な空気だった)。となるとやはり複製には対応した方が良さそうで、自分も複製をやるクライアントを書き始めたが、その頃には既存のソルバーがかなりのクオリティで、最終的にも太刀打ちできるケースはほとんどなかった。一応、300ケース中7ケースで自分の出力を使ってもらえたらしいが、無念…。

どのマップでどのアイテムを買うかの購入計画については、自分がナップサック的にやれば行けるでしょみたいな事を言いだした手前実装した。

チームではサーバで各問題への回答を集計していて、各提出のステップ数と購入したアイテムを記録していた。この提出群を用いると各提出の相対スコア 1000*log(areaSize) * Tbest / Tself を計算できて、その提出の価値を(相対スコア - 使った金額)、使った金額を容積として、各問題から1提出えらべるという制約の元、稼いだ金額を上限にナップサックする感じ。

貧乏だったので、クローンを2個買う解とか調べなくて良くない…？という意見もあったが、富豪はやる可能性があるし仮想敵としていれておくべき、と主張して調べてもらった。結局クローンを2個使った提出も採用されていたらしいので良かった。

ふりかえり

目に見える貢献は、入力コンバータ、問題ジェネレータ、提出セレクタくらいで、要となるソルバーは微小な貢献に終わってしまった。ちょっとしたものを書くのは早かったっぽいけど、マラソン的な部分がやはり弱いらしい。

チーム内ランキングページやサーバ提出スクリプトを次々仕上げていくインフラ班も見事で、初参加の身としてはみんなしゅごい…という感じであった。

チーム戦は機会が少なくICPC以来では…くらいの感じだったが、なかなか業務だけでは見られにくい同僚の凄さなんかも見られて刺激になり、面白かった。次があれば、もうちょっとマラソン的なところで貢献したいなというのと、重要そうな局面は予定を空けておくようにしたい。