hogecoder

tsutaj 競技プログラミングの記録

HTTF 2024 (AHC027) 参加記

AtCoder 競プロ (マラソン)

HTTF 2024 (AHC027) に参加しました。最終順位は 71 位でした。コンテストを通して焼きなましを初めてフル活用したので、いろいろ振り返りをしていきます。

問題はこちらです。

atcoder.jp

最終的な解法

超かんたんに説明すると、こういう解法でやりました。

  • 左手法で壁を伝う + 左手法で通らなかったところを DFS して初期解を作る
  • 初期解に対して時間いっぱい焼きなまし

seed = 0, score = 1516668

最終提出はこちらです。

atcoder.jp

左手法で壁を伝うだけでは、当然中のセルが埋まっていかないので、そこは DFS で埋めて初期解としました。DFS で全セルに訪問したら即座に帰るようにはしましたが、それ以外はサンプルの方法と同じです（ここどうにかしたかった・・・）

焼きなましについては、もういろいろ頑張りました。最終的に採用された近傍は以下のとおりです。

  1. 経路の挿入
    • 汚れやすさが大きいエリアに出張して戻ってくるイメージで、新しく経路を追加する
  2. 経路の削除と追加
    • ランダムに経路を削除した後、削除されたことで一度も訪れなくなったセルに少なくとも 1 回は訪れるように、経路を追加する
  3. 経路の削除のみ
    • 削除しても全セルを訪れている場合に対応
  4. 経路スワップ
    • 経路が overlap しないように気をつけながら、セル c_1 から c_2 までの経路を 2 つ選んで、その 2 つを入れ替える。
  5. 経路移動
    • セル c_1 から c_2 までの経路を任意の位置に移動させる
    • 移動させた経路については、元いた場所を通過させるように使うので、移動先の時刻で訪れているセルを p とおくと、 p から c_1 までの経路と、 c_2 から p までの経路も追加される。
  6. 隣接スワップ
    • 操作列（LRUD からなる列）で隣接している 2 文字を入れ替える
    • 種類の異なる 2 文字をスワップするとき、訪れなくなるセル・新たに訪れるセルが必ず 1 つずつできて他は（訪問時刻の意味でも）変わらないので、スコアの差分計算ができる

スコアの更新頻度が高かった近傍は 2 番, 4 番, 6 番 です。特に隣接スワップはコストの差分が O(\log L) *1 かつ戻すのも楽なのでかなりイテレーションが稼げました。

1 番, 3 番, 5 番は、スコアの更新頻度が少ない（特に 1 番は序盤しか効かない）ものの、無くすとスコアは悪化してしまいます。状態を大きく変えるのが偉いのかなぁと思っています。

左手法・初期解・焼きなまし後のビジュアライズ結果

すべて seed = 4 の結果です。

左手法 (score: invalid)

壁をつたっているだけなので、これではそもそも正解できません。

初期解 (score: 14355524)

左手法で壁をつたっていた解に対して肉付けが行われていることがわかります。

記事をかいてて思ったけど、この初期解あんまりよくないね・・・もっと良い作り方ができればよかったけど、わからなかった。

焼きなまし後 (score: 8066790)

焼きなましでけっこう改善します。焼きなましすごい。

良かった点

  • 焼きなましをフル活用できた
    • 今まで貪欲ばっかりやってて、あまり焼きなましまでたどり着けたことがなかったんですが、今回はしっかり使えたのでよかったです。
  • 隣接スワップを思いついた
    • 終了前日に思いついて、実装したら順位が 40 個くらい上がりました！その日は 10 時間くらい何も進捗がなくて心が折れかけてたんですが、最後に改善できて本当にうれしかったです。やっぱり軽い近傍は考えるべきだなあ。
  • 1000 ケースを回して、 N ごとに結果を比較して良し悪しを判断できた
    • 毎回やってることではあるんですが、たくさんのケースで比較するようにしています。コンテストの順位は相対評価スコアで決まるので、前の結果を s_p、今の結果を s_c としたとき、 \log\left( \frac{s_p}{s_c} \right) の正負を見て良し悪しを判断していました。こうすると N が違ってもそこそこ似た指標で比較できると思っています。

反省点

  • 初期解はもう少しいい感じに求めたかった
    • 解説放送や感想戦を見ていると、まだ訪れてことがない地点までの最短経路で辿る人が多いみたい？それはコンテスト中に試せるべきだった（コンテスト中には思い浮かんでいなかったんですが）
  • ある地点から 1 周している経路をひっくり返す近傍は思いつきたかった
    • 下のスライドで「操作 2」として紹介されている近傍のことです。

  • もっと良い（速い？）近傍を思いつきたかった
    • 最終提出であっても Time Limit を 5 倍とかにすると有意にスコアが良くなるので、時間内に良い解にたどり着いてない感じでした。こういうときは効率の良い近傍にするか速くするかのどっちかしかないと思うので、そこの引き出しをもっと増やしていきたい気持ちです。

ちょっとずつ AHC の勘所がつかめてきたかな？という感じです。とはいえ初期解とか細かいところとか、まだまだ粗い部分もあるので、そこがもっと詰められるようになりたいところ。次もがんばります！

*1:より詳しくいうと、スワップによって新たに訪れるセル・訪れなくなるセルの訪問回数をそれぞれ n_1, n_2 としたときに O(\log n_1 + \log n_2) くらいになっていて、 n は小さいのでかなり軽い