AHC003 参加記 - ごりちゃんがゆく

AHC003、参加しました！！

きっと参加記を書きますと言ったので、参加記を書きます！！

#AHC003 お疲れ様でした
94161824540 点でしたシステス前136位ぐらいで個人的に健闘しました！
画像はseed 0です
序盤200ターンは横→縦→横みたいに曲がる回数は高々2回
残り800ターンは毎ターンdijkstraしました
距離の予測に使うスコアは終盤ほど重みをつけました
あとできっと参加記を書きます pic.twitter.com/bBMw91YEpi
— prd🦍 (@prd_xxx) May 30, 2021

↑にも書いていますが、自分としてはなかなか健闘できたと思っています！
誰かの役に立つかは不明ですが、今回は思考の流れを軽くメモしていたので、時系列でやったこと試したことを書いていきます！

問題概要などは割愛します！ (問題文をみてね)

63.1G

縦に動いて横に動くと、このスコアになります！

76.2G

とりあえず横→縦→横と動くことにして、どの縦線を使うかを全探索しました。
(縦座標または横座標が同じ場合は一直線)
基本的に、 $\frac{(得られた距離の合計)}{(通った回数)}$
のような感じで推定をしました
(実際には得られた距離には $\frac{(縦の辺数)}{(縦+横の辺数)}$
を掛けて使用しました。)
そのために、各縦線の得られた距離の合計と通った回数を管理する2つの配列を用意してやりました

81.1G

↑の方針に加え、横線についても管理するようにして、縦→横→縦　の選択肢も加えました。

85.2G

情報の粒度を細かくしました。
横線についてはすべての $h_{*,*}$ 、縦線についてはすべての $v_{*,*}$
について管理するようにしました。
基本の移動ポリシーは変わらず、横→縦→横か、縦→横→縦です
それと、申し訳程度に乱択を加えました。
縦に動く回数を $v$ 、横に動く回数を $h$ とすると、 ${}_{v+h} C_v$ の動き方のうち $100$ 種類程度を毎ターン評価にいれました (しかしあまり意味なかったと思う)

ボツ案

さて、各辺を簡単に評価できるようになったところで、考えました
これは、みんな大好き 最短経路問題 じゃないか！！
グラフのサイズも小さいし、これは Warshall–Floyd が使えるだろ！と思いました
ところが掛け算をしたぼく
「 $30 \times 30 = 900$ 頂点、これは $O(V^3)$ が間に合わない！」
「そうだ頂点を減らそう、 $i, j$ がともに偶数の頂点だけ使えばサイズが $1/4$ になる！」
「 $225$ 頂点なら $100$ ターンごとに $9$ 回の最短距離更新をしても間に合うな」
との思考で改善をたのしみに勇んで書いたコードは
80G 点ほどでした。(ボツ) ¹

89.1G

よくよく考えると、Warshall-Floydはとても無駄が多いことに気づきました
例えば頂点 $(0,0)$ から $(5,5)$ へ移動する場合に、明らかに $(10,10)$ みたいな頂点は経由しないです。
(※ Warshall-Floyd はすべての頂点を経由してみることを試します)
経由するべき点は殆ど、 $(s_i, s_j)$ と $(t_i, t_j)$ を含む長方形に収まるだろうと考えました
そこで思いついた！
例えば左上から右下に動くとして、右か下にしか移動できない場合の最短経路は、dp で求まる！
しかもどのような移動によって最短路を更新したか、記録すれば dp復元 もできる！そして、この dp こそ、 $O(N^2)$ なのでなんと毎ターン求めても余裕で間に合うのです！
また、ビジュアライザをみて気づいたのですが、
同じ縦線 (または横線) に含まれる辺は、値が近い ことにも気づきました。
序盤はあまりクネクネ動かない方が精度よく情報を集められるだろうと考え、序盤200ターンは横→縦→横か、縦→横→縦の移動ポリシーを残すことにしました。
残り800ターンをdpにしたら良い感じでした。

89.8G

移動がdpでうまく書けたので、今度は距離の予測をどうにかしたい気分になりました。
例えば $(s_i, s_j)$ から $(t_i, t_j)$ の(グラフ上の)距離が $3$ で、ジャッジから得られた距離の実測値が $20$ だとします。
このとき、今までは $3$ つの辺に対して、「得られた距離」に $\frac{20}{3}$ を足し、「通った回数」に $1$ を足していました。
これを改良し、「得られた距離」にフィードバックする距離の長さは、予測される距離で按分してあげることにしました。
つまり $3$ つの辺の現時点での予測距離が、 $3, 5, 7$ だとすると、それぞれ、
$20\times \frac{3}{3+5+7}$ , $20\times \frac{5}{3+5+7}$ , $20\times \frac{7}{3+5+7}$
を「得られた距離」として足してあげることにしました。
これによって予測がちょっとだけ改良しました！

90.3G

↑の予測をちょっといじって、ターンが経過すればするほど (=新しい情報ほど) フィードバックを重めにしました。
(純粋に turn / 100 みたいな値を掛けた)
90Gに乗りました！

93.3G

ここで、例えば左上から右下に動く場合は右か下にしか動かないことを仮定して dp をしていたけど、これを疑うことをしました。
(時には一見遠ざかるような移動も役に立つのではないか？？)
そこで気づいちゃったんですね！
dpが間に合うということは、dijkstra も間に合うんでない？？
実際 dpは毎ターン $O(N^2)$ 、
dijkstraは毎ターン $O(E \log V) = O(N^2 \log N^2)$
で、 $\log$ が掛かる程度なんです！
実際書いてみたらPyPyで間に合いました！²
そして、スコアはここで大きく伸びました！うれしい！
上下左右の移動を許すことで、一見遠ざかるような移動でも改善できる移動は見逃さなくなりました！
これで伸びるの、わりと非直感的だなーと思って面白かった。

93.7G

ここで新たな武器を手にしました
ローカルで $100$ ケース実行して集計するシェルスクリプトです！ (書きました)
これまでは手元で数ケース叩いて改善してそうな雰囲気があったら投げていたのですが、 $30$ 分の提出制限はたくさん試すのには向かないと気づきました
いくつかパラメータをいじって猿のように試しまくりました！³
すると、フィードバックに掛けていた値 turn / 100 を (turn-152) / 8 にすることで、試したなかでは一番改善がみられてそうでした
これの意味は、 $200$ ターン付近で得られた情報は序盤 $200$ ターンで集めた情報の $6$ 倍の価値があって、 $1000$ ターン付近では $106$ 倍の価値があることを意味します
なぜこの値で改善するのかは、なぞです

94.08G

序盤 $200$ ターンの横→縦→横か、縦→横→縦の移動に関しても、フィードバックの距離は予測距離で按分して求めてあげることにしました

94.16G

序盤において、一度も通っていない点は初期値を定めて計算に使っていたのですが、これを使う機会をできるだけ減らそうと考えました。
同じ縦線 (または横線) に含まれる辺は、値が近い ことには気づいていたので、初めて通る縦線 (または横線) を記録するとき、直接通っていない箇所にもほんのりフィードバックしてあげました。
がっつりフィードバックでは悪化するようで、ほんのりが良さそうでした (重み 0.01)
微妙に伸びました。
他色々試したけど、結局このスコアは抜かせず、最終スコアとなりました