第13回 Asprova プログラミングコンテスト（AtCoder Heuristic Contest 070）に参加しました。
4時間の短期コンテストです。短期では今回から生成AIの利用が原則禁止となりました。
問題の本質を理解できている感じはしないながら、地道な実装で 54位 でした。嬉しいので参加記録を残します。
問題の概要
- 原点
(0, 0)から移動しつつ、移動先にお札を設置することを 10,000 ターン繰り返す - 移動は、事前に決めた3つの距離
(a1, b1) (a2, b2) (a3, b3)に限定される。また、上下左右にループできる - 毎ターンどこかのマスに怪異が発生するが、お札が近いほど怪異の危険度を低減できる
- 怪異が発生するマスの全貌・順番は事前に分かっている
- 怪異は後半に発生するものほど強い（危険度が大きい）
これらの前提下で、すべての怪異についての危険度をできるだけ低減するように「3つの移動距離」と「移動経路」を構築する問題です。
問題イメージ
移動は右|下方向にしかできませんが、端でループするので問題ありません。上手くやれば最終的に全マスにお札を設置できそうです。
考えたこと
- 序盤の怪異は無視して、お札を全体に均一に設置すると良さそう？
- 全マス埋めるゲームっぽく見えて、そうでもなさそう
- スコアの差分計算が厳しそう、山登りや焼きなましは厳しいか
- ビームサーチは有効そうに見える
実装したこと
最終イメージはこのようになりました。お札を設置できてないマスは 1,400 くらいあります。この辺改善すればもっと上位に行けたのかな？
移動距離を決める
同じ座標に到達しないようにするため、素数付近が良さそう？
色々なパターンを手で試して、序盤は (14, 33), (7, 1), (5, 9) で固定しました。
最終的には処理時間が余ったので、おおよその範囲でランダムに決めて一番良かったやつを選択する「乱択プレイアウト」をしました。
移動経路を決める
最初に、将来的に発生するものも含めた危険度を全マス分スコアリングしておきます。
毎ターン、お札を設置した際の低減度の合計が最も良い手で貪欲に移動させました。
これ自体はお札との最短距離を BFS で更新するだけなので、比較的高速に動作します。 自分の実装では 50回 程度な全体処理を回せたので、移動距離の乱択に回しています。
最終的には、5,000手以降先の怪異はほぼ無視するようなスコア補正を加えました。 この工夫で 3% 程度スコアが改善しました。
怪異が発生済みのマスについては 危険度 = 0 としてクリア処理をした方が良さそうだと思ったのですが、これはスコアが安定して下がりました。 厳密な計算が必ずしもスコアに寄与するわけではないのか・・要勉強です。
「考えたこと」で記載したあたりの考察は全部吹っ飛びました。 序盤に均一に設置する、だけ実装しましたが全体を貪欲で回す方が結局強かったです。
感想
今回順位は 54位 と良好（自分の中では）でしたが、スコアの絶対値だとトップから 1.6倍 程度離れています。問題の理解度が全然足りていないな〜と痛感しています。
強い人のまとめを見ると、移動距離の組み合わせについては理想的なパターンがあるようです。 その辺は公式の AHCラジオ でも語ってくれそうな気がするのでとても楽しみですね・・！
