HACK TO THE FUTURE for Youth＋オープンコンテストに参加しました。
良い感じに連結して道を作る問題でした。
このコンテストは珍しくチーム参加可能、言及OKというお楽しみコンテストで、
ゆうさん、hotpepsiさんとチーム「びっくりするほど共通点がない」で参加しました。
結果は提出339チームのうち17位(オープンだけだと117チーム中9位)でした。
問題
50x50のグリッド空間があって、ポリオミノ(ブロックが連結したもの)があるよ。
指定された点全てにブロックがあるようにポリオミノを置きつつ、ブロック全てを４近傍で連結させてね。
ポリオミノごとにコストが決まっていて、総コストが低いほど高得点だよ。
やったこと・考えたこと時系列
前日夕方～夜
チームメンバーが3人決まる。
オープン側はチームだと入賞特典が一切ないのだけど、開始前にチーム登録を済ませておきたい気分だったので勝手にSlackを立ててチーム名を決めに入る。*1
メンバー同士の共通点から名前を付けられたら良いなと思い、使用言語などの自己紹介をし合った結果、共通点が、無い…！
ゆうさん「びっくりするほど共通点がない」
私「もうそれがチーム名でいいのでは」
というノリで、チーム名決定。
hotpepsiさんはcompetitiveprogramming.infoというサービスを作った方らしい。凄い。
図を書ける場所が欲しいよー、と言われたのでGoogleのスプレッドを共有。GoogleのOffice系は図はちょっと書きづらいですね。miroとかいうサービスもあるらしい。
開始直後～1時間
社会性の塊なので、全員席にいる状態で開始。*2
皆で問題を読んで考察する。
誤読したり気付かない点があったりして、皆で読み合わせ出来るのありがたいの気持ちに。
Twitterを見るとA問題が配点割合的に大きそうということで、専任を置く方針に。
A問題 私（手動で頑張る）
B問題 hotpepsiさん（直線で繋げる）
C問題 ゆうさん（貪欲で点までの距離の総和を最小化）
で作業開始。
採用しなかったアイデアとして、焼き鈍しの他、各マスを左上として各ポリオミノを置くかで全探索チックに探索するというものも。C問題なら10種で50x50なので、11^2500から枝刈りする感じ？有効パターンが多すぎて流石にきついですよね…。*3
開始1時間～2時間
A問題は1.1M点ほど取得。（当時オープン3位タイ）
BC問題が何点まで取れるか不明だったので、相談して私もBC問題に着手。*4
相談中～BC着手直前にもAの解が生えてきて、A問題1.2M。
開始2時間～3時間
hotpepsiさんとゆうさんのプログラムがそれぞれ完成。
ゆうさんのプログラムがBで1.7M、CでTLE。Cは倍速化しないと無理らしい。
一応自分のプログラムは書きつつ、ゆうさんの押し上げを優先する方針に。
実装間に合わないよー、と言っていたらゆうさんがソースを丸ごとくれた。
Pythonをそのまま使うのは無理だったけど、コードが短かったので勇気が湧いてきた。*5
hotpepsiさんもゆうさんのプログラムをC++移植する方針に。
開始3時間～4時間
いや、誰もC通せないのは不味くない？
ということで、枝刈りや打ち切りしてでもとりあえず通そうぜと提案。
hotpepsiさんのアルゴリズム提案と私のセコい技*6で、残り25分でC問題をAC。
枝刈り部分にパラメータを使っていたので、25分で出来る事と言えば…
パラメータガチャの時間だああああ！！！
ということで、C問題を1.616M→1.651Mまで伸ばして終了。
総論
結果的にはPython使いを先行させて押し上げるという動きになりました。実装難易度に対して時間が足りない問題だったのもあって、上手くはまりましたね。*7
先行して結果を出してくれたゆうさん、別角度から攻めつつ的確なアドバイスでCを通せるところまで持っていってくれたhotpepsiさんに感謝…！
おまけ
A問題の手動での解き方
以下のことを意識しました。
・1つのポリオミノで多くの目標点を踏む
・目標点を踏むついでに遠くまで伸ばす
・手動焼き鈍し(一部を破壊して作り直す)
全体的にはコスト3ポリオミノの遠くまで伸ばす能力が高く、それをどれだけ活用できるかが重要な気がしました。また、全体的に横に伸ばす能力が弱い一方で縦はTが強く、孤立した場所は縦に繋ぐ方針が強そうでした。
感想
チームで出るマラソンなんてそうそう無いからという理由で急造チームを組んでみましたが、チームならではの戦い方が出来て楽しかったです。今度は実装でも活躍したい。
