wataの日記スマートフォン用の表示で見るwataの日記プロコンや研究の話など書くかもこの広告は、90日以上更新していないブログに表示しています。今年もUnagiチームのいつものメンバーで参戦。今年の問題は二次元グリッド上でロボットを動かして全部の空きマスを塗りつぶすという基礎タスクに、追加仕様でブーストアイテムなどが加わっていくというものだった。使用言語をRustに統一Unagiチームは例年言語を統一せずに全員異なる言語で参加していたせいもあって、得意・不得意が割とはっきりしていて、問題をたくさん解くタイプは得意(複数ソルバで独立に解けるので)、対戦AIは苦手(複数AIで協力ムズイ)、仕様追加も苦手(追加されるたびに全ての言語で同じものを実装する必要が...)という状況だった。2017年のpunterが対戦AI+仕様追加で惨敗したのを反省して、去年はソルバ班がchokudai以外Rustに統一され(元々chokudaiがRustに切り替えると言い出したはずだったのだが...)、今年はついにchokudaiがC#を一行も書くことなく、ソルバ班全員がRust統一となった(インフラ班はGoも使っていた)。書き始めてかなりびっくりした。統一できて、やっぱりかなり良かった。画像は開始前に練習に便利なサービスを教えてあげている様子です。去年の参加記(http://wata-orz.hatenablog.com/entry/2018/07/26/194842)にある通り、言語統一の利点は非常に大きく、ソルバ1つをパーツに分けて皆で作っていくことで、各自が自分の担当部分を改良すれば全体のスコアが伸びて分業が捗った。Rustに統一する利点としては、速度が十分速い・バグが出にくい・他の人が書いたコードを使い回ししやすい(自然とグローバル変数を使わなくなる&変更されるものにはmutが必要になるので)というのがあると思う。実際、今回も色んなパーツを別々に書いて組み合わせたら一発で動くことが多かった。学習難易度が高いとよく言われるけど、競プロやICFPCのプログラム書く程度なら意外と簡単なので、バラバラの言語で参加してる他のチームもぜひRustに統一してみてはいかがでしょう!Rustの勉強を「チュートリアルを眺めてABCを3問解く」くらいにしてICFPC本番で使ったけど、書くだけなら意外といける言語ね。(1500行くらい書いた)Rustおもったよりこわくない。chokudaiがソルバのメインロジック部分を書き始めるという分担でスタートした。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チームしか居なかったので、大量の報酬コインを得ることが出来た。その後は順調にコインを稼いでいって、おそらく最終的には一番金持ちになっていた。ソルバの方は、chokudaiが引き続きブースター完全無視左手法ソルバの改良を続け、自分は殆どのマップでcloneを購入出来そうなのでclone部分の最適化をし、iwiが局所改善(塗らない動きを最短路で置き換える)を書いた。cloneは区域に分割するのはやはり境界部分で無駄が発生する&均等に分割するのが難しいので、一体のつもりで生成したアクション列をk等分するという方針に切り替えた。manipulatorは妥協してkの倍数個回収し全員に同じだけ使うことにした。分割後の開始地点への移動分無駄が発生するので、終点の方が近かったら反転させたり、ビットDPで誰がどの区間を担当するかを最適化したりした。三日目chokudaiは引き続き左手法を最強にし、iwiが最適な購入計画をナップサックで求める部分を書き、自分はiwiの局所最適化プログラムを引き継いて枝刈り探索による最適化を追加した。今年もチームUnagiのいつものメンバーで参加。月別アーカイブはてなブログをはじめよう!wata_orzさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。