はじめに
これはAHC018におけるPsyhoさんの戦略を翻訳したり考察してみたりするメモです。
自分用にまとめる意味もあるので、わかりにくかったり間違っていたりするかもしれません。
原文
https://github.com/FakePsyho/cpcontests/blob/master/atcoder/ahc018/approach.md
最終方針（本人のブログの説明準拠）
- 水源、家、あらかじめ決められた格子点からなるグラフを作成します。エッジのコストは、その2点間のマンハッタン距離と、その2つの特定のセルでのこれまでの掘り出し統計に基づいています。
- 任意の水源（水源または既に水が流れているタイル）と任意の家の間の最短経路を見つける。
その経路の中で、まだ完全に掘られていない頂点を選択する。- タイブレーク1: これまでに掘った数が少ない
- タイブレーク2: 目標までの距離が近い。
- 完全に掘り尽くされた頂点だけを含む経路ができるまで、(2)を繰り返す。その後、水から家までの完全な経路を作り、タイルを1枚ずつ順次発掘していく。
- (1-3)を完了するまで繰り返す。
それ以外に特別なことはしていない。
グラフのエッジコスト計算や穴を掘るパワーは一見ランダムに見える関数を使っているが、パラメータ調整の結果です。
もう少し詳しい解説
いやいやいや、特別なことはしてないとか言われても、、
よくわからないですね？
いろいろ動かしながら咀嚼してみました。
グラフの作成
水源、家、あらかじめ決められた格子点からなるグラフを作成します。
の部分ですが、
これは距離18を基準とした格子点を考えます。
格子状のグラフは他の多くの参加者も考えていたように思いますが、
Psyhoさんのグラフでは、斜めにも辺を持つ点が特徴的です。
始点(y,x)に対し、
(y+18,x)
(y,x+18)
(y+9,x-9)
(y+9,x+9)
の4点を終点とした辺をつなぐといった形です。
うろ覚えですが、Twitter上の議論で「斜めの辺を持つとマンハッタン距離が縦横の2倍になるのでコストが平等にならない」といった内容を誰かが言っていた気がしますが、斜めの辺は単純に縦、横方向の長さを半分にすれば辺の長さは変わらないですね。
この(y+9,x-9),(y+9,x+9)を実現すため、始点は9ずつずらしながらグラフを作っています。
また、距離18以内に家(図中赤)がある場合は格子点でなくても辺をつなぎます。
そして、距離18以内に水源を見つけたらどの点と組になるかを覚えておきます。(図中オレンジ)
※ソースコードを見る場合、build_graphがグラフ構築の実装ですが、通常の辺と水源への辺は保持の仕方が異なる点に注意しましょう。水源だけvsに保存されます。
以下はシード6に対する初期グラフです。
最短経路を求める
グラフを構築したら、全ての家を始点としてダイクストラ法で最も近い水源(水源とつながった岩盤を含む)を求めます。
ダイクストラ法自体はググるなりしていただくとして、ダイクストラ法を適用するにあたり、辺のコストを定義する必要があります。
まず、座標(y,x)の岩盤の固さを低めに想定した値を$low_{y,x}$, 高めに想定した値を$high_{y,x}$と置きます。
これらはそれぞれ以下の式で計算します。
$low_{y,x} = 岩盤が破壊される前に掘ったパワー累積値+1$
$high_{y,x} = これまでに掘ったパワー累積値$
そして、座標(y,x)の見込みコストを$value_{y,x}$としたとき、
座標(y,x)の岩盤が破壊済みの場合、
$value_{y,x}=\frac{low_{y,x}+high_{y,x}}{2}+10$
座標(y,x)の岩盤が破壊されていない場合、
$value_{y,x}=\lfloor\frac{high_{y,x}(105-4\log_2C)}{(\ln{(high_{y,x}+1)})^2+1}\rfloor+160$
で計算します。
岩盤が破壊済みの場合は単純に期待値ちょい高めで計算してるだけなので直感的ですね。
問題は、岩盤が破壊されていない場合、、
よくわからないのでグラフを見てみましょう。横軸が$high_{y,x}$, 縦軸が未破壊時の$value_{y,x}$です。
グラフを見るとわかりやすいですね。
この式を用いることで、
$high_{y,x}$が低い時は$high_{y,x}$よりかなり高めに、
$high_{y,x}$が高い時は$high_{y,x}$より少し高めに
見積もることを意図していそうです。
言い換えれば、あまり掘ってない時は「もっと固いかも？」、ある程度掘っていれば「もうそろそろ掘り終えてるのでは？」と考えるということです。
さて、座標(y,x)の見込みコストを$value_{y,x}$を定めたので、これを使って辺のコストを定めます。
座標(y0,x0)と座標(y1,x1)をつなぐ辺のコストを$edge_{y0,x0,y1,x1}$とした時、
これは以下の式で計算します。
\begin{aligned}
edge_{y0,x0,y1,x1} = & (|y0-y1|+|x0-x1|) \times(C+0.5(value_{y0,x0}+value_{y1,x1})) \\
& +C\;\;\; ※(y0,x0)が未破壊の時だけ加算 \\
& +C\;\;\; ※(y1,x1)が未破壊の時だけ加算
\end{aligned}
これはそんなに難しくないですね。
2点間の全点が2点の平均コストで埋め尽くされていると仮定してマンハッタン距離でかけてるだけです。
掘るパワーの決め方
さて、最短経路が決まったら順番に岩盤を破壊していきます。
この時、どの程度のパワーで掘るかも体力消費を抑える上で重要です。
まず、経路の始点は$power=2C+30$で掘り始めます。
1回で掘りきれなかった場合は、前回より少しだけ大きなパワーで掘るのを繰り返します。
始点を掘り終えたら、経路を1歩進んで順に掘り進めるだけです。
始点以外は1歩前に掘った岩盤の固さがある程度わかるため、隣の岩盤も似た固さのはずだと仮定し、最初のパワーを決めます。
まず、1歩前の岩盤の固さの期待値は以下の式で計算します。$low_{y,x}$, $high_{y,x}$は前述の式を使います。
$exp=\frac{low_{y,x}+high_{y,x}}{2}$
掘りたい岩盤の固さも$exp$だと仮定し、
1回あたりパワーpで掘った場合、
約$\frac{exp + p - 1}{p}$ 回で掘りきれると仮定します。
※分子に$p-1$が足されているのがしっくりきませんが、expの計算時に2で割った際に切り捨てられる端数を考慮してるんでしょうか。
岩盤を$\frac{exp + p - 1}{p}$ 回掘った場合、
必ず体力を$\frac{exp + p - 1}{p}C$無駄にします。
また、パワーpで岩盤を掘って岩盤を壊すことに成功した場合、0以上p-1以下の体力が無駄になります。
つまり、平均$\frac{p}{2}$の体力を無駄にします。
これらの仮定から、無駄にする体力$waste$を以下の式で表します。
$waste=\frac{exp + p - 1}{p}C+\frac{p}{2}\times weight_C ※$
※$weight_c$はCに応じてあらかじめ定めた重み
掘るパワーは1以上1001以下の範囲で$waste$が最も低いものを選択します。
おわりに
今回、AHC018の1位、Psyhoさんの解法を咀嚼して、ブログに記載されていない部分も紐解いてみました。
基本方針は「マップをグリッド状に分割してグラフを構築」「辺にコストを持たせて最短経路を掘るのを繰り返す」という多くの参加者がやっていたであろう方針だったため、Psyhoさん自身は「特別なことはしていない。」といった言葉を残されています。
「パラメータ調整をがんばっただけ」ともコメントされていたので、鵜呑みにしそうでしたが、いざ細かく見てみると、体力を無駄にしないために期待値を計算していたり、細かい考察の結果が伺えます。
本記事に記載しきれなかった細かい調整もコードには散見されるので、より細かい工夫が気になる方はぜひコードを読んでみましょう。