AtCoder Heuristic Contest 018 ~Excavation~ 参加記

RECRUIT 日本橋ハーフマラソン 2023冬(AHC018)に参加して、
1,359,993,445,143点の 229位/1,082人 でした。

解法や所感について書いていきます。

解法

大筋の流れ

クラスカル法の要領で接続する2点の候補を決める。
実際に接続する前に掘削コスト調査を挟み、良さそうな経路があったら接続を実行、無かったら次善次々善の候補の調査へと進む。
という感じでした。

もう少し具体的には、下記の手順を取っています。

  1. 水源・家の中からペアを作って、マンハッタン距離をコストとする形で優先度付きキューに突っ込む。
  2. コストの小さい順にペアを取り出す。以下の条件を満たす場合は3に進む。そうでなければ2を繰り返す。
    • ペアの中に、水源と接続していないものがある
    • ペアの2点を対角点とする長方形の中に、他の家や水源は含まれていない
  3. 掘削コストの低そうな経路を調査して、有ったら実際に繋ぐ(調査の方法は次節に記載)。
    無かったら接続はせずに、その候補を優先度付きキューの最後に回して*1 2 に戻る。
  4. 接続経路の中で、全水源・家に対してそれぞれ最短の点を調べ、そのペアを優先度付きキューに加える
  5. ゲーム終了していなければ、2 に戻る

掘削コストの低そうな経路の調査方法

前節の 3 でやっている、2点間の接続経路の調査方法。

  1. 2点を対角点とする長方形内で、xy座標両方が11の倍数である点を調査点とする*2
  2. 調査点を所定の深さまで掘る*3
  3. 岩盤破壊できた調査点を対象に、縦横の接続だけで始点から終点まで接続できるなら、その経路を採用して終了
  4. 掘る深さを増やす
  5. 掘る深さが調査上限に達したら、接続に向かないと判断して調査打ち切り。そうでなければ、2に戻る。

パラメータチューニング

ローカルで1,000ケース周して絶対スコアの合算値を見る形で、手動チューニングを行った。
幸い(?)今回は実行時間を使うような解法ではなかったので、1回周すのに20秒くらいで済んだ。

チューニング対象は、以下。

  • 掘削処理の1回あたりのパワーの大きさ
    • C ごとに設定した
  • 調査点の間隔
  • 2点間の接続調査を打ち切る深さ の上げ幅*4

パラメータチューニングが順位の伸び的には一番効いた。

課題を感じたところ

  • 最短経路しか調査していないため、迂回するのが有力なケースに弱い
  • 調査点の目が荒くて、岩盤が厚いところを通ってしまっている
    • チューニング結果が良かったのがこれではあったが
  • パラメータチューニングが手動
    • Optuna 使いたかった

他にも細かいやりたいことは山ほどあったが、コンテスト時間が全然足りませんでした。。

テストケース0000のビジュアライズ結果

提出コードはこちらです。
Submission #39277152 - RECRUIT Nihonbashi Half Marathon 2023 Winter(AtCoder Heuristic Contest 018)

コンテスト終了後の所感

TLを見て活かせそうだと思ったこと

  • 接続調査のところはA*を使うのが良さそう
  • C に応じて調査点の間隔を決めた方が良さそう
  • ローカル実行時、絶対スコアを見てたけど上手くなさそう。頑張って相対スコアの近似を作るべき。

AHCラジオを見て

AHCラジオ: RECRUIT 日本橋ハーフマラソン 2023冬(AHC018) - YouTube

  • 入力値についての出題者意図とかが聞けて面白かった
  • 水源同志は連結している扱いにしておくと実装が楽って話を聞いて、なるほどと思った

その他雑感

  • 実行時間をめちゃくちゃ余らせたけど、どう使うのが良かったのだろうか。
  • パラメータチューニングが滅茶苦茶効いた。珍しい問題だなと思った。
    • 掘削1回あたりのパワーをいじってから一気に順位が上がった
  • 終盤までスコアが全然伸びなくてとてもつらさを感じた。最後の3時間で300位くらい伸ばした。
  • 最初に問題文読んだ時は「この情報量じゃ運ゲーにならないか?」と思った。実際は全然そんなこと無かったですが。
  • 数日経つまでサンプルコードがあるのに気づかなくて、みんな初動強いなと焦っていた
    • サンプルコードがまずまず強いのも悪い(適当)
  • 盤面生成の Perlin noise のあたりの話をどう解釈すべきかで困惑した。調べてみて、なだらかに変化するってところの情報が肝で、パラメータ推論(?)的なことは求められてないんだろうな という判断というか決め付けというかをして進んだ。
    • AHCラジオを聞いた感じだと、出題者意図的にはそれで良さそうに聞こえた

*1:コストを一定量加算して優先度付きキューに突っ込み直す。キューが一巡したら、許容する掘削コストを上げる。

*2:こうすることで、別調査と調査範囲が被ったときに、調査点を使い回せる

*3:ただし、辿り着けないことが分かっている調査点は対象から外す

*4:調査方法の5の打ち切り判断に使う