HACK TO THE FUTURE 2024 （AtCoder Heuristic Contest 027）参加記

はじめまして、notkamonohasiと申します。

HTTF2024（AHC027）に参加しました。プレテス45.6Gで最終順位41位でした。

コンテスト中に考えたことや、その考えに至った経緯をぼんやり書きたいと思います。

atcoder.jp

解法概要

  1. 貪欲＋ダイクストラ法で初期解を生成。評価関数の設計を頑張る
  2. 長さが3～6のパスを破壊・再構築。差分更新を頑張る

Score = 1396597 (seed=0)

前提知識

解法詳細

厳密性はなく、お気持ちが多めとなっています。

初期解

初期解構築パートは以下の2つに分かれています。

  1. 次どこに行くか
  2. どの道を通るか

この2つを全てのセルが訪問済みとなるまで繰り返します。計算時間は0.3秒前後でした。

次どこに行くか

以下の三要素がバランスされているセルを目標とするのがベストだと考えました。

  1. 汚れがたまっているセルに行ってほしい
  2. 未訪問のセルに行ってほしい
  3. 今いる場所から遠すぎない場所に行ってほしい

色々調整した結果、評価関数は以下のようにすると貪欲だけで良い感じになりました。

{f_{target}(x,y)=\frac{Sv}{\sqrt{d}}}

S：セル(x,y)の現在の汚れ

v=\left\{ \begin{array}{ll} 10\quad (未訪問) \\ 1\quad (訪問済) \end{array} \right.

d：現在位置からセル(x,y)への距離

特に \sqrt{d}がスコアに効き、目標地点が近すぎず遠すぎないセルになってくれました。

どの道を通るか

考えたいのは以下の三要素です。

  1. 汚れがたまっているセルを通ってほしい
  2. 未訪問のセルに通ってほしい
  3. 遠回りしすぎないでほしい

前節のお気持ちとは3のみ異なっています。具体的な評価関数は以下で、この評価関数をダイクストラ法の辺の重みとします。

f_{route}(x,y)=(D-S)*v

D：汚れ増加の総和\sum d_{i, j}

S：セル(x,y)の現在の汚れ

v=\left\{ \begin{array}{ll} 2\quad (未訪問) \\ 1\quad (訪問済) \end{array} \right.

注意点として f_{route}は負の値を取り得ます。ダイクストラ法は辺の重みが非負である必要があるので、厳密解を出すことはできません。しかし、厳密解を出すのは計算時間的に厳しいですし、大体良い感じであれば良いのでこれで妥協します。

山登り

初期解は細部が非常に適当なので、改善の余地があります。残った計算時間を使って山登りで解を更新します。

山登りの遷移の流れは以下です。

  1. 長さ3～6のパスを削除
  2. 削除したスタート地点とゴール地点を繋ぐパスのうち、規定長さ以下を全探索
  3. 一番スコアが良かったパスを採用・状態を更新

愚直に実装するとスコアの計算には O(L)必要なので、遷移回数を稼ぐために差分計算で高速化します。

総経路長が変わらないときの差分計算は簡単な一方、総経路長が変わった時の正確な差分計算は分かりませんでした。そのため、総経路長が変わった時は以下の様にスコアを推定しました。

f_{score}=totalScore+\alpha\times \bar{S} \times \Delta t

\alpha：不確実さを考慮した係数

\bar{S}：平均汚れ

\Delta t：総経路長の符号付増減

要は「総経路長が増えると罰則を与え、減ると報酬を与える」をしています。

不正確なスコアなので、更新時に正しいスコアを計算して、元のスコアを下回った場合更新しないことにしています。

1回の遷移にかかる計算時間は長く、seed=0でも遷移は20000回程度しか回っていません。特に Nが大きいケースでは試行回数が足りず、計算時間を短くできれば更にスコアを上げられる状態です。

コンテスト中に考えたこと

今回のコンテストでは、初期解の構築に結構リソースを割きました。理由は以下の2つです。

  1. スコアを維持したまま解の形を大きく変化させるのが不可能に見えた。そのため、山登りパートを頑張っても、初期解が悪いと良いスコアにならないと思った。
  2. 開始4時間でitigoさんが出したスコアが中盤まで2ページ目に残っていた。このことから、難しいことをしなくても最終38Gを出せる解法が存在することに確信を持てた。

短期コンはともかく、長期コンでは最近の傾向・難易度を考えると、中盤までは貪欲をじっくり考える（＝問題固有の性質に向き合う）のが良い進め方だと思っています。

感想

問題設定の簡単さに対して、初期解を頑張る必要がある点と、計算時間が全く足りない点が特に難しかった。

ビジュアライザーの機能が充実していて、ビジュアライザーを眺めながら局所的な改善ポイントを見出せたのが良かった。

最後に

AtCoderの皆様、そしてtsukammoさんをはじめとするフューチャー社の皆様、コンテストを開催してくださり、ありがとうございました！

次回HACK TO THE FUTUREも楽しみにしています！

おまけ

就活＆研究ヤバい