マラソンコンテストのHTTF2021決勝オープンに参加してきました。
予選落ち用の誰でも参加できるコンテストです。
結果は本選出場者と合わせた提出者のうち、31/217位。
かつてない好成績で満足です。 atcoder.jp
問題
問題はマイニング。某建設案件かな？ 鉱脈を掘ると利益が得られるが、隣接する採掘済のマス数に応じて採掘コストが変化するというものでした。
掘る順番こそあれど、"いつ"という時間の概念がほぼ無い問題のため、典型問題に対するアルゴ知識が薄めでも力押しで(ある程度は)なんとかなる問題だったと思います。一方で掘り始めは赤字スタートになるため、方針が立たないと正の点数を取るのが難しく、スタートはもたつく問題でした。
データの特性としては、一様ランダムではなく偏りが存在するもので、掘る順番通りに外側から探索するのではなく、内側に埋まっている美味しい場所を中心に探索するのが良さそうでした。
方針
ローグライクゲームのマップ自動生成に近いことをしました。
まず部屋に相当する、利益の大きい領域を抽出します。次に部屋同士および鉱山の外をそれぞれ最小コストで繋げば、おおよそ最適解が得られるだろうというものでした。上手く行かない部分は、３部屋以上を組み合わせて最適な経路を組む場合と、[利益＜コスト]である採掘済のマス数に応じて利益が出るマスの扱いですね。
結果としてもまさにそんな感じで、採掘済隣接マスが1のときの利益は上手く拾えましたがそうでない部分で稼ぎが甘かったです。
方針の詳細
１．[利益＞コスト]の場所を抽出。
２．利益大マス同士が連結しているもの単位でグループにする。
３．グループに対して２，３マス連結かつ[利益＞コスト/隣接数]の場所も巻き込む。
４．グループ同士の結合コストが最小、かつ結合コストが弱グループの利益より小さく、かつ結合コストがいずれかのグループの外周からの採掘コストより小さいものを結合する（結合できなくなるまで繰り返す）
５．グループの評価が外周からの採掘コストより高いものを掘っていく。
６．あとは場当たり的に利益が出る場所があれば掘っていく。
細かいテクニック
コスト節約
コストは
・k=1 1/1
・k=2 1/2(-50%)
・k=3 1/3(-16%)
・k=4 1/4(-8%)
でk（４近傍で隣接する採掘済マス数）の増加に対して減り方が一律でないので、なるべくk=1で取ることを避けると少しだけスコアが稼げました。取ることを決めた領域に対して、kが大きい場所から順に取るようにすると良かったです。（1/3ほど実装し損ねているような…？）
反省会
解説配信的なものは今のところ無いようですが、出題者の方によるとフローを使うらしいです。用語が全然分かっていないので余力のあるときに勉強しようと思います。
上位陣と差が付いたのは、利益が[コスト/3＜利益＜コスト]のようなマスを広く取れるかという部分のように見えました。コストを払うときにkがいくつか想定できずにシミュレーションに困ったのはありますが、矩形領域で取っていけば比較的計算しやすそうですね。
あとは例によってマラソン的な最適化を全く行っていないですね…。領域同士の結合はコスト最小から順番に結合というルールがかなり強く思えたので、必要が薄かったといえばそうなのですが。方針を立ててちょうど８時間使い切って実装が尽きたというのもあり、そこまで後悔は無いかも？
要望的なもの
紛らわしい用語が多くて混同しがちでした。
・データに含まれる「外周」と、データに含まれない「鉱山の外部」
・「利益」に含まれない「コスト」
ビジュアライザは良いところも悪いところもありました。
・一瞬だけ最終スコアが出て、その後は現スコアが出る挙動は考察で使いやすかった。
・コストは表示してほしかった（採掘過不足の判断が付かない）
・全体的に暗めで、特に簡易表示でないものや利益の低い箇所は見づらかった。
・簡易表示の、採掘済マスも色が見える印のつけ方が良かった。
全体としては、楽しみつつ考察の助けになるビジュアライザでとても良かったです。（お前は何様）
完走した感想
コンテスト中は問題に言及禁止なのもありましたが、オープン参加者が少なくてTwitterで苦しむ仲間を見れなかったのがちょっと寂しかったです。皆も、走ろう！（マラソンハラスメント）
