AHC018 366位振り返り(ダイクストラ法など)

2023年の2/18から2/26にかけて開催された"RECRUIT 日本橋ハーフマラソン 2023冬（AtCoder Heuristic Contest 018）"に参加させていただきました.
私13thmiko(AtCoder:th13miko)は暫定397位, 最終366位, Performanceは1433となりました.

最終解法

大まかな解法は以下の通り.

1. マップ上の特定の点を試掘する
2. 試掘の結果から大まかな岩盤硬さ分布を推定する
3. 推定結果をもとにダイクストラ法を使用, 一番少ないコストで水路を作れる家を探す
4. 実際に水路を掘る
5. 3-4繰り返し

試掘

この問題の重要な? 性質の一つとして
"最初からマップ上のいかなる点も採掘することができる"
というものがあります. 家や水源などの特定点から掘り進める必要がないということです.

なので, 例えばマップを一定の大きさをもった小さい領域に切り分け, その領域の特定点(例えば中心とか)を試し掘りする... なんてことができます.
この試掘結果によって, 領域がどのような硬さの岩盤でできているか推定することもできるようになります.

岩盤硬さ分布推定

私の解法では最終的に, 同じ場所を3回程度試掘し, 掘れたか掘れないか, 掘れたならば何回の試掘で掘れたかによって段階的に推定値を出し, その結果を(事実上)領域全体に適用しました.

なお, 最終プログラムでは全域を試掘するのではなく, 後に述べるラフ探索でダイクストラ法を動かすときに必要になったところだけ試掘するように実装しています.

ルート決定

ルート決定はダイクストラ法で行いますが, 通常のマップ($N \times N$)上で行うのではなく, まずは上に上げた約$16 \times 16$の少領域1つをまとめて1頂点とするようなグラフ¹上で, 自身が所属する領域から最寄りの水源が所属する領域までの最短距離を探索します. 以下, このような探索をラフ探索と呼ぶことにします.

実際に掘り, ルート探索へ戻る

最初に挙げた手順だと"一番少ないコストで水路を作れる家を探"し, その後"実際に水路を掘る"とあります.
これは(まだ水が通っていない)すべての家のうち, 最も少ないコストで水路を作れる家がどれかを(上で上げたラフ探索を使用して)まず全探索します.
その後, 最も少ないコストで水路を作れる家へ実際に水路を掘ります.

この問題の性質の一つとして
"水が通っている場所まで水路を通せばよい"というものがあります.
当然のことといえば当然のことですが, 必ずしも水源まで水路を通す必要はなく, すでに作られた水路に合流する水路を作っても良いということです.

この性質のため, どこかの家へ水路を作るごとに他の家の最短水路は変わっていきます.
というわけで, 1本掘るたびにわざわざ全探索し直しているのです.

"既に水路が作られているか"の判定はUnion-Findによって行いました.

また採掘時のパワーは一つのテストケースに一律の値で, $40 \sqrt{C}$としました.
どのように検証したか忘れましたが, 確かこれが効率的な設定だったはずです.

参考ビジュアライズ

このような解法による$W = 4, K = 1$の問題($seed = 9722301943906086$)に対する回答のビジュアライズを御覧ください.

等間隔で存在する灰色だったり白色だったりするところが試掘している点です.
アニメーションを掲載できればもっとわかりやすく試掘してる感が出せるんですが, アニメーションGIFを載せようとしたらアップロード上限に引っかかってしまいました.
pastebinに回答を貼り付けておいたので, seed値を使って公式ビジュアライザからアニメーションは御覧ください.

振り返り

今となっては当時何を考え何をしていたのかあまり覚えていませんが, できるかぎり振り返ってみます.

2/18-2/22のどこか

問題を見る. インタラクティブ形式と知り若干の絶望感.

思いついたアイデアを書き出す. 最終的に半分も実現しなかった.

2/23

一番近くの "水源" まで水路を掘るプログラムを試作.
経路は長方形の2辺を使うような形で道中の硬さを考慮せず, パワーも固定値100と適当.

一番近くの "水路" まで水路を掘るようにプログラムを変更. ここでUnion-Findによる水路管理が実装される. なおこの時点でも水路を引く順番は適当.

$C$によってパワーを変更するように. 平方根を作った式はこの頃できた.

採掘ごとにパワーを変更するプログラムの制作を試みたものの, スコアを改善できず, 断念

2/24

これまで適当に決めていた"水路をどの家に引くか"の順番を最近水路へのマンハッタン距離が短いものから引くように設定

2/26

サウジカップを見る. パンサラッサ優勝(もしくは日本勢優勝)の瞬間を見れて良かったです.

ラフ探索を実装 ほぼ正式版と同じプログラムになる

これ以降試行錯誤するも改善せず

評価できた取り組み

筆者は今回が(事実上²)AHC初参加でしたが, 今後のAHC, もしくは競技プログラミング全体, 更には競技シーンに限らないプログラミングにも活かせそうな取り組みをいくつか行うことができたように感じました.
以下その振り返りです.

Git

過去にも何度かGitを使用したことがありましたが, いずれもなんとなくの使用であったため, 特に他人とリモートリポジトリを共有する場合などは迷惑をかけることが多かったです.

今回バージョン管理としてのGitにはじめて触れたことにより, 何をすべきか, 何をすべきでないかが大まかにわかったような気がしています.

テストプログラム

ローカル環境のテスターが公式から配布されていますが, 手動でコマンドを打って実行する形だと1ケースずつしか実行できません.
というわけでランダムなシードを300ケースほど生成し, すべてのケースについてテストするプログラムを作りました.

またデバッグのためのログを出力しようとしたのですが, 標準出力は問答に使わなければいけないので, プログラムに特定のオプションを与えたときだけ別のファイルへログを出力する機能も追加しました.
詳細は省略しますが, とても役に立ってくれました.

などと誇っていた私ですが,

ローカルテスタは解答プログラムの出力をそのまま出力ファイルに書き出します。 解答プログラムは、# から始まるコメント行を出力に含めてもかまいません。

ジャッジプログラムはコメント行を全て無視するため、コメント行を出力するプログラムをそのまま提出可能です。

と問題ページに書かれていたのを執筆中に見つけて真顔になりました. 専用ログファイルいらんかったんかい...
皆様も問題ページはよく読みましょう.

反省すべき取り組み

一方, 今後改善すべき行動も多数ありました.

日記

この記事の振り返りは提出記録やGitのCommit記録, あとは執筆時点で残っている私の記憶を頼りにして書いたものです.

AHCのような比較的長期のヒューリスティックレースは事実上の研究ですので, 研究ノートを何らかの形で残しておく必要があるように感じます(一般の科学研究のような厳密性はなくても良いとは思いますが).

pythonを使用したこと

今回は言語として一貫してpythonを使用しました.
みなさま御存知の通りpythonは動作速度が遅いです. 今回はいわゆる焼きなまし法のような反復計算をする必要がないので, たとえpythonだとしても提出には特に問題がありません.

しかし, 多数のケースをテストする場合は別です.
300ケースをテストできるプログラムを作成したと言いましたが, このプログラムの実行には2分ほどかかっています.
一方このコンテストの優勝者Psyhoさんが書いていた解説記事によると, 氏のテストプログラムは10000ケースを1分未満で実行できてしまうようです.

多数のケースを高速に処理できるようになると, 統計的に精密性の高いデータを得やすくなります.
そういったデータが手に入れられると, 例えばパラメーターの調整がやりやすくなったりもします.
アルゴリズムレースでpythonを使っていたので, その時のライブラリなどの資産を活用するためにpythonを使用しましたが, これからはC#などを使用したほうが良いのでしょう.

入力の傾向

ヒューリスティックレースでは入力の傾向を利用するのが(多分)重要事項です.
しかし, AHC018の入力生成方法を私は理解できませんでした(まずParlin noiseを知らん).

一応, 入力ファイルを見るだけでも, "なんか20ぐらいの数値が多いなぁ"とか"硬いとこ掘らないほうが良さそうだなぁ"とか, そういうことはわかるはずです. 実際私はそのような情報を(若干ながら)利用してはいます.

しかし, 岩盤硬度の統計を取るとか, もっとそういう深くまで踏み込んだ分析をすれば, もっと何かわかったのではないかと思うところがありました.

他の方の解説を見て

ガウス過程...?
ベイズ推定...?
知らん...何それ...怖...

終わって初めてハッシュタグ#AHC018を見に行ったら知らん単語が飛び交ってて宇宙猫してました.
いずれにせよ, 線形でも何でもいいから補間ができるということや, 水路の本採掘時に推定値を更新できるということを思いつかなかったのは失敗だったかもしれません.
ある意味ラフ探索, ラフマップ戦略の敗北でしょうか.

また, bio4etaさんも解説記事の最後で触れていらっしゃったのですが, 上位勢の方を見ると, ほとんど最短経路の部分しか試掘していないことがわかります. 一体あれはどういうトリックなんでしょうか. A*アルゴリズムを使うとあんなふうになるんですかね?
解説を読んでそれを理解できるよう, もっと多くの知識, 経験が欲しいと, そう思う私でした. なおこの解説は知識量の如何にかかわらず読みにくい模様

ひとまず, 次回までにC#とoptuneとGitを練習することにします.

1. プログラム上で"ラフマップ"などと呼んでいました. ↩

2. AHC017は参加登録し, リアルタイムで問題を読んだものの未提出撤退 ↩