コンテストを開催していたので開催記です。あまりしっかりしたものではありません。
注意
⚠️⚠️⚠️今回の問題設定はフィクションです！！⚠️⚠️⚠️
普通に犯罪なので唐突に破壊衝動に駆られても町の建物を爆破させてはいけません！！！
そもそも爆発物の所持・製造・使用もすべて犯罪です！！！！
死刑、無期または7年以上の禁固・懲役に処される重罪です！！！！！絶対に真似しないように！！！！！！*1
開催したいきさつ
実は、6月ごろからyukicoderでコンテストを開催したいとやんわりと思っていました。
その後、だいぶ間が空きますが9月ごろにyukicoderのスコアコンテストの開催経験があるお二方と話す機会がありまして*2、yukicoderのスコアコンテストは思ったより需要があることがわかったので開催することを決意しました。
まあ特に深い理由があってのことではないですが、楽しんでいただけたのであれば幸いです。
問題作成
爆弾ですべてを破壊するネタはなんかのゲームをやってた時に降ってきました。とりあえず大本はG - Strongest Takahashiを参考にして作りました。*3
当初は、「10*10マスを爆破」「上下左右を爆破」「×印のように爆破」のように考えていましたが、たぶんあんまりおもしろくないかなと思い、爆破の形をランダムにしました。
また、最初は「すべての建物マスをカバーする配置を見つける」だけのものを考えていたのですが、要素はある程度多い方がいいかなと思ったので、はるく君をスポーンさせました。移動のコストについてはB - Garbage Collectorの形式が良いと思いそのまま採用しました*4。爆弾をもちすぎるとコストが大きく、だからと言って小分けに買いすぎると爆弾屋が全滅する可能性もあり、けっこうちょうどいい塩梅になったと思っています。*5
実はこのネタは10月に思い付いたもので、6月には別の案があったのですが、6月に思い付いたものは競技性に欠けそうだったこと、ビジュアライザが単調になって盛り上がらなさそうだと思い没になりました。*6
問題ページを作成するにあたり、No.5017 Tool-assisted Shooting - yukicoderを大きく参考にしました。この場でplatinumさんに感謝申し上げます。
ビジュアライザの作成は、先述の問題の形式と同じようにSiv3Dでやろうともしたのですが、どうしてもPythonに慣れてしまったのもあって、Pythonで完結させたいと考えていました。
そこで、pygameというモジュールに行きつき、調べまくって何とか完成させました。実装にあたり、100ターンごとに状況を保持しているので、100000ターンもあるとさすがに重いです*7。
ところで pygame というやつ使ったことなかったんだけどこれ実は AHC デバッグにめちゃくちゃ便利だったりしますか・・？
— きり (@kiri8128) 2023年11月17日
難易度がやや高いこと、昼に参加しにくい人も参加してもらいたいことを考えて期間は3日間としました。金曜のコンテストがつぶれるという相当なむちゃぶりなのに対応してくださったyukiさんには感謝です。
問題への言及
フォロワー全員唐突に破壊衝動に駆られて住んでいる町にあるすべての建物を爆破させようとしている
— いなにわ (@inani_waon) 2023年11月17日
えっ、怖い…*8
爆弾屋も建物なので爆破されちゃうの因果応報ですき#yukicoder #HakaiProject
— いなにわ (@inani_waon) 2023年11月17日
爆弾屋を破壊すると罰金も考えましたが全部壊す方が面白そうだったので却下しました。
はるく君は爆弾被弾しまくってるのに、なんで生きているんでしょうか？#yukicoder #HakaiProject
— tipstar0125@競プロ (@DragonEngineer1) 2023年11月17日
注...彼は特殊な訓練を積んでいます。
爆弾屋のある町、何？
— G4NP0N (@G4NP0N_kyopro) 2023年11月17日
治安が終わっておりますね…
解法
writerの想定解
0を出力するだけのものも一応正当な解です。50点
サンプルコードはすべての建物を壊しているので、得点が跳ね上がります。9,148点 しかし、あまりにも無駄が多くこれを改造しても得点が上がる望みは薄いです。
思いつきやすいであろう貪欲は、「一番壊せるところを壊すことを、全て壊れるまで繰り返す」です。はじめに爆弾を買い込んでこれを行うと比較的良い点数が取れます。1,637,160,602点
writerの最高得点は、これを4分割した区画それぞれで行う方針です。1,739,837,672点
絶対爽快だけどコンテスト的にはあまり得点は高くなく…
ちなみにContestantの方の中では以下のが一番近いと思います。
#yukicoder #HakaiProject はこんな感じ。
— EvbCFfp1XB(C7BMkOO7Qbmcwck7) (@EvbCFfp1XB) 2023年11月19日
25x25 の4つの領域に分けて、各領域の中心辺りで破壊しました。
爆弾屋、爆発させる位置・種類・順番を変更して焼きなましました。 pic.twitter.com/L2P4Qgdk5g
Testerさんの想定解
tester 解は適当に貪欲しただけです
とのことです。貪欲で2G超えられるのすごい…
参加者さんの解
だいたいここから見れます。
どうやら上位の方は爆破のさせ方は貪欲で移動経路を焼きなまし等で決めているそうです。復習しないと…*9
今回の問題については、iiljjさんの以下の発言が最も的を射てると思っています。
問題のストーリーに反して，少ない爆弾をチマチマ仕入れて緻密に爆破していくパズルが模範解答というね#yukicoder #HakaiProject
— si (@iiljj) 2023年11月19日
コンテスト中
1日目
初めのうちはあまり参加者が来ないとは予想していましたが、まあそれは予想通りでした。
開始2時間でsample.cppに軽微なミスがあったのを指摘されました。反省。
あんま時間ないし順当に1.5G程度の貪欲解が出て終わるかなと思いきや、 まさかのW/Tともに1日目でbin101さんとwanuiさんに抜かされました。何事…
爆弾所持歩行コストがバカにならないとは思っていましたが、まさかここまで影響があると思っておらず…
暫定順位です。翌朝まで寝るので質問対応ができなくなります。
— はるく@競プロ (@halc_kyopro) 2023年11月17日
すでにW/Tが2人の方に打ち破られました(!?) pic.twitter.com/vWrFIqqtlF
2日目
W/Tともに複数人に抜かされました。
wanuiさんとbin101さんが首位争いをしており、見ていて楽しかったです。
また、このころから数名ビジュアライザを共有してくれました。ありがとうございます。
暫定順位です。W/Tともに抜かされまくりました。
— はるく@競プロ (@halc_kyopro) 2023年11月18日
日曜20:00までですので、まだ参加していない方も明日ぜひ参加してみてください。#yukicoder #HakaiProject https://t.co/rChm6tlXVt pic.twitter.com/4BJlI0M3Bb
3日目
ここまで正直言ってあんま参加者数が伸びず心配だったのですが、この日は潜伏勢がめちゃくちゃ沸いて昨日上位だったメンツが軒並み抜かされていました…
bowwowforeachさん、rhooさん、Kiri8128さんが首位争いに参加しており、少し見れば首位が変わっていてめちゃくちゃ熱い展開でした。*10
また、当初は想定もしていなかった2.9Gが出てしまいました。私の解より1.7倍くらい効率的なの怖い…
結局rhooさんがぎりぎり勝ちました。あらためておめでとうございます。
終了です、おつかれさまでした！
— はるく@競プロ (@halc_kyopro) 2023年11月19日
1位はrhooさんでした、おめでとうございます。
解法共有は以下のタグを使っていただけると助かります。#yukicoder #HakaiProject pic.twitter.com/U0S3lv6ki9
感想
たくさんの方に参加していただけて、何より無事に終われてよかったです。Clarがほとんどなかったのもよかったです。
期間が普段より長く、ゲームバランスとかを少し心配していましたが、最終日にも多々良い解が出たので結構期間はちょうどよかったと思っています。金曜日がつぶれるのはさすがにあれなので同じ形式でまたやるとしたら土日になりそうではありますが。
改めて、コンテスト開催の場をいただいたyukiさん、Testerのjupiroさん、先駆者のplatinumさん、参加者の皆様に感謝申し上げます。本当にありがとうございました。
