RECRUIT 日本橋ハーフマラソン 2023冬（AtCoder Heuristic Contest 018） 3位のモンテカルロ解法
はじめに
RECRUIT 日本橋ハーフマラソン 2023冬（AtCoder Heuristic Contest 018）に参加し、私のRatedコンテスト最高順位である3位に入りました。
この記事では私の解法と、参加記代わりに解の変遷について書いていきます。
最終的な解のビジュアライズ(Seed=12)
問題概要
岩盤を破壊して家から水源までの道を開通させる。
岩盤には頑丈さがあって、頑丈さに応じて破壊するために必要なパワーが違うのだが、必要なパワーが初期の入力に与えられず実際に壊しながら推測が必要。
家から水源までの道が開通するまでのパワーと掘削回数をできるだけ少なくする。
解法概要
以下のような方針で解いた。
- 斜めの格子上に代表点をとってグラフを構築
- モンテカルロ法のシミュレーションにより、有力な代表点を決定して、有力な代表点をパワー上限ありで試しに掘ってみる
- 試し掘りを繰り返し、開通した代表点のみを経由することで家から水源まで到達できるなら、その経路を開通させることに決定する
- 代表点の間の点を開通させるとき、近くの開通済みの点から頑丈さの区間を推定し、期待値DPで求めたパワーで掘る
いわゆる格子タイプの解法になっている。私は斜め線を多用するため、それに合わせて格子も斜めのものを使っている。
試し掘りのフェーズと経路開通のフェーズは完全に分けている。交互に行うパターンと比べると、多様な経路の選択肢をなるべく後の方まで残せると考えたためこの方針にした（あと実装が楽）。
モンテカルロ法によって試し掘り対象の代表点を選んだ部分がこの解法の特徴的な部分だと思う。コンテスト中は「今回はモンテカルロ回だな」と思っていたのだが、コンテスト後に他の人の解法を見るとモンテカルロ法を使っている人がほとんどいなくて驚いていた。
解法詳細の前に
頑丈さの知識について
セルの頑丈さのについて知識は [下限,上限] の区間として表せる。ここで 下限 =max(10, セルが壊される前までの合計パワー + 1) 、上限 = min(5000, セルが壊された時の合計パワー) となる。
実際の頑丈さはこの区間内に含まれるが、テストケース生成方法からすると恐らく分布は一様ではない。ただし近似的に一様であるとして扱うこともある。
期待値DPによるパワー決定
もしある岩盤について頑丈さの区間が正しく分かっていて、分布が一様であるなら、その岩盤を破壊するための最適なパワー配分はDPにより求めることができる。
dp[T] = (残りの頑丈さ上限がTであるとき、その岩盤を破壊するための消費体力の期待値)
のように定義したとき、
dp[T] = min(e(1), e(2) , ..., e(T))
e(p) = p/T*(p+C) + (1-p/T)*(p+C+dp[T-p])
のような更新が可能である。ここでeの引数pはパワーを表す。
実際に必要なのはdpの復元であり、dpの更新時にminになるパワーを powers[T] = (残りの頑丈さ上限がTであるときの最適なパワー) のようなテーブルで保存しておく。
頑丈さに下限と上限があるときには powers[上限-下限] + 下限 のようなパワーにすればよい。
実際には分布は一様ではないし、頑丈さの区間は近くの点を用いて推定することになるため、この期待値DPの前提を完全に満たすことはない。ただ、「Cが大きいときは大きく刻む」「Cが小さいときは細かく刻む」というパワー調整を自動で行える利点があるため、嘘であっても適宜使っていく。
解法詳細
概要の箇条書きを再掲する。
- 斜めの格子上に代表点をとってグラフを構築
- モンテカルロ法のシミュレーションにより、有力な代表点を決定して、有力な代表点をパワー上限ありで試しに掘ってみる
- 試し掘りを繰り返し、開通した代表点のみを経由することで家から水源まで到達できるなら、その経路を開通させることに決定する
- 代表点の間の点を開通させるとき、近くの開通済みの点から頑丈さの区間を推定し、期待値DPで求めたパワーで掘る
基本的にこの順に沿って説明する。
グラフの構築
斜めの格子上、右端と下端から格子間隔を空けた点、水源、家を代表点にして、代表点を頂点にしたグラフを構築する。上下左右斜めに近接した頂点間で辺を結ぶ。
結果として図のようなグラフになる。黒い点が格子点、青い四角形が水源、緑の三角形が家であり、灰色の部分は辺である。
格子を水平垂直よりも斜めにしたほうがスコアが良かったのだが、理由はよくわかっていない。縦線・横線と斜め線で辺のマンハッタン距離が均一になることが有効に働いているのかもしれない。
格子のサイズとして、縦横の間隔は17、斜めは(縦8,横8)と(縦9,横9)の2種類の間隔ができる。明らかに縦横の間隔を偶数にして斜め線を均一にするほうが綺麗なのだが、ハイパラ調整の結果奇数になってしまった。
斜め移動について
個人的には斜めの辺を用いる斜め移動（ギザギザ移動）を積極的に行うようにしていた。格子点上で斜めに柔らかい点が並んでいるときはその間を通るのが良い場合が多かったという経験則による。縦や横に柔らかい代表点が並んでいるとき経路を通していいなら、斜めで同じ判断をしてもいいだろうと考えていた。
実際のところは斜めありとなしでどちらがいいのかは分かっていない。
モンテカルロ法による試し掘り
やりたいことは、代表点グラフ上で家から水源までの経路のうち、なるべくコスト（＝頑丈さ）の低い経路を見つけることである。代表点を試し掘りしてコストの低い経路を見つけることにする。
無作為に試し掘りを繰り返すと無駄に体力を消耗してしまうため、なるべく最終的な解に入る可能性が高い、有力な代表点だけ試し掘りしたい。
今回は有力な代表点を見つけるために、代表点グラフ上でモンテカルロ法を用いることにする。乱択シミュレーションを何度も行い、実際に経路上に現れることが多い代表点が有力であるとみなす。下図のようなイメージで試し掘り対象を選ぶ。
試し掘りの流れは以下のようなものである。
- 以下の処理を100回程度繰り返す
- 辺のコストを無作為に割り当てる
- そのグラフ上で各家から水源までの最短路を求める
- 最短路上にある各頂点について、選択回数を1増やす
- 選択回数が最も多い代表点を選んで試し掘りする
- ただし、これまで試し掘りした回数が0回の代表点は優先的に選ばれるようにする
以下、細かく説明する。
辺のコストを無作為に割り当てる
各代表点について頑丈さの [下限,上限] の範囲が分かっているため、その範囲から代表点のコストを無作為に割り当てる。ただし、ここでは一様分布にしない。
なるべく低いコストが選ばれやすいように、sqrt(下限) ～ sqrt(上限) から一様に乱択し、選ばれた値を2乗する。入力生成を真面目に再現したほうがいい気がするが、手を抜いている。
なお、sqrtと2乗で説明したが、実際にはパラメータPに対して (下限)^(1/P) ～ (上限)^(1/P) から乱択した後P乗する。「なんとなく2乗、なんとなく平方根」にしたものは、肩に乗せる数字をパラメータ化しておいて後から調整するのはヒューリスティック典型（？）。
辺のコストは(両端の2頂点のコスト平均)*(辺の長さ)とする。
各家から水源までの最短路を求める
辺コストがあるグラフでシュタイナー木のような問題を解くことになるが、モンテカルロの繰り返し回数を確保するために軽い解法が求められる。今回はダイクストラを繰り返す貪欲法によって解くことにする。
まず家1から最も近い水源までの経路をダイクストラで求める。続いて、家2から最も近い水源までの経路も求めるのだが、このとき既に求めた家1から水源までの経路上にある頂点も実質水源であるとみなしてよい。言い換えると、家2から「水源または既に水源までの経路がある頂点」への最短経路を求めることになる。家3以降も同様である。
こうして作成された最短路上の頂点について、選択回数を1増やす。
選択回数が最も多い代表点を選んで試し掘りする
まだ開通していない代表点のうち、モンテカルロ法での選択回数が最大の代表点を試し掘りの対象とする。
ただし、これまで一度も試し掘りをしていない代表点は、選択回数に約2倍の下駄を履かせて、試し掘りの対象に選ばれやすいように調整する。
この試し掘りは必ず開通まで掘るわけではなく、パワー上限ありで掘って開通しなかった場合は次の試し掘りに移行する。対象の点を初めて試し掘りするときは合計パワー44以下、2回目のときは合計パワー170以下、3回目以降は合計パワー300以下までになるよう掘る。
パワー上限を頑丈さの上限とみなし、先述の期待値DPによるパワー配分で掘削を行う。
経路決定
試し掘りを終わらせてよい条件
試し掘りを繰り返すことで、代表点グラフ上の点がいくつか開通した状態になる。この開通済の頂点（とそれらを結ぶ辺）だけを通ることで全ての家から水源に到達できるなら、試し掘りを終了可能とする。
ただし、終了可能になった直後に経路決定すると良い経路にならない場合があるため、終了可能になった後、最大20回まで試し掘りを行って終了する。
経路決定
試し掘りが終わったら、モンテカルロのシミュレーションとほとんど同じ方法により家から水源までの経路を決定する。今回は以下のようにコストを割り当てる。
- 開通済みの代表点：(コスト上限+コスト下限)/2
- 未開通の代表点：コスト5000
そのうえで、モンテカルロのシミュレーション時に行ったものと同様にダイクストラの繰り返しにより経路決定をする。ただし、今回は乱択貪欲を数回行って合計コストが最も小さくなる経路を選ぶことにする。
もう少し真面目にシュタイナー木を解いてもいい気がするのだが、今回の解法では経路はほぼ一択となるので手を抜いている。
代表点の隙間を開通
ここまでで代表点間の経路を選んだので、後は代表点の間にある点を開通する。各代表点ペアについて、素直に片方の代表点に近い方から順々に開通させる。
ここでパワーの決定が問題になるのだが、隙間の点はこれまで一度も掘っていないため、頑丈さ下限は常に10、上限は常に5000であり、この点自身の情報は役に立たない。
そこで近くにある破壊済みの点から頑丈さ区間を推定することになる。傾きは全く考慮していないが、したほうが良かったかもしれない。
具体的な方法はひたすら思い付き＆ハイパラチューニングに任せたため理論立てて説明できないのだが、結果として以下のように開通させている。
- 頑丈さ下限の推定値：一番近い開通済み点の頑丈さ下限 * 1.05
- 頑丈さ上限の推定値：一番近い開通済み点の頑丈さ上限 * 1.0 ~ 1.15 (Cの値によって違う)
- 初回パワー：(頑丈さ上限の推定値 * 0.7 + 頑丈さ下限の推定値 * 0.3)
- 2回目以降のパワー：上限' = (頑丈さ上限の推定値 - これまでこの点を掘削した合計パワー) として、期待値DPで求めたテーブルから 上限' において最適なパワーとする
解の変遷
参加記代わりに、自分の解法がコンテスト中にどのように変化していったかを書いていく。ビジュアライザの見た目に大きな変更があるものを中心に記載する。
問題をみて最初に作ってみたのは、「全部の点をパワー50で叩いた後に、開通した連結成分を頂点として全域木を作る」という解法だった。これはサンプル解にボロ負けする。（画像はSeed=12。これ以降も同様）
さすがに全部の点を叩くのは効率が悪すぎるので、次は隙間を開けて格子上の点を全部叩いて初期の連結成分を作ってみた。これでもサンプルに負ける。
もう少し最初に叩く点を減らすため、格子上の点をパワー100で叩き、開通した点を起点に上下左右へパワー100で開通できる限り伸ばす、という方法で初期の連結成分を作った。これでようやくサンプルに勝利。
全域木を作る方針だと、最終的に何にも使われない経路を開通することもあった（上の画像の左下領域など）。そのため、なるべく無駄な経路を作らないようにしたかった。
格子上の点を叩き、開通した点を頂点としてシュタイナー木のようなものを作ることにした。ただし辺のコストは距離の2乗に比例させる。
ということで、無駄な経路をなくすことに成功。頑張って焼きなましで実装したが、実際のところ貪欲で十分であることが分かった。
上の画像を見ると、右上領域の硬い岩盤に経路を通していることが分かる。現状の解では開通していない点は全て同様の頑丈さであると決めつけているため、そうなってしまう。そのため硬い岩盤を避けたい気分になった。
硬い岩盤を避けるためにはまだ開通していない代表点を叩いて頑丈さを推定する必要があるのだが、全ての代表点を叩くのは効率が悪い気がした。できれば最短経路に使われる可能性が高い有力な代表点だけ叩きたい。
ぼーっと考えてみた結果、最短経路に使われやすい代表点を探すには実際に最短経路を作ってみればいい、という考えに至った。そこで、最短経路を作るシミュレーションを行うことで試し掘り対象を決める、モンテカルロ法を行うことにした。
結果、右上領域の硬い岩盤を試し掘りして硬いと認識できるようになり、避けるようになった。
家と水源の配置を見るだけでも、使われる可能性がほぼないと分かる代表点がいくつもある。それなのに最初に1回、代表点全てを叩いているのは無駄だという気分になった。そのため、最初に格子上の点を全て叩くのをやめ、最初からモンテカルロ法をすることにした。
なんとなく格子を縦横ではなく斜めにしたらスコアが1割くらい改善して驚いた。縦線・横線・斜め線でマンハッタン距離が均一になるからだろうか？
そこからビジュアライザの見た目上はあまり変更なく様々な改善を行った最終的な解。格子の間隔はかなり荒くなった。
終わりに
私の解法の中には理論的に説明できないマジックナンバー・アドホック処理が大量に含まれます。どうも今回の問題はそこがかなり重要な位置を占めるようであり、「思いついたことをとりあえず実装して実験を回してみる」タイプの私と相性が良かったようです。
クラウド上の仮想マシンをずっと稼働させていたため結構なお値段になりました。ちょっとしたコーディングとテストケース実行を繰り返す場合サーバーレスのほうがいいんだろうか？
Discussion