AtCoder Heuristic Contest 003 やったこと
自分がやった解法の簡単な方針と観察を書きます．
観察
得点
番目 (
) のクエリに対する最短路長を
、出力されたパスの長さを
とすると、以下の得点が得られる。
式を見ると，クエリが進むにつれて点数の荷重の割合が増えていきます．このことから，クエリの前半でおおよその長さを調べ，クエリの後半で最短路を走ることが良さそうに見えます．
入力の生成
完全なランダムではないのが特徴です．ここでは分かりやすく の場合に着目してみましょう．( 横 or 縦 ) 一直線にベースとなる長さがあり，そこに乱数で上下する形になっています．つまり，大体横一直線と縦一直線は同じ長さになっています．
の場合はこの横一直線と縦一直線に，もう一分割が加わる違いがあります．
観察まとめ
上記の 2 つの観察から，クエリの序盤で各縦と横の大まかな長さを求め，残りは最短路でいくのが良さそうに見えてきます．
クエリ序盤
おおよその縦横の長さを決めに行きます．おおよその縦横の長さがしりたいので，基本的には一直線の歩き方をします．まだ，見ていない縦と横を中心に ( 最大でも 2 回しか曲がらない ) ような感じで移動します．
そして，全ての通った辺に ( パスの長さ ) ( 始点と終点のマンハッタン距離 ) の情報を保持させます．各辺の暫定的な長さは，各辺が保持している長さの平均としていきます． ( わかりにくいですが，平均の平均を長さとしてる感じです )
ある程度，情報が溜まったところで，各縦と横がだいたい同じ長さの性質を利用して，全辺のだいたいの長さを推定しに行きます．各辺において，( の場合にも対応できるように ) 近傍の長さの平均として，先程の path の平均のリストに加えます．
クエリ後半
最短路をもとめればいいので，ダイクストラで求めました．あと，各辺の微妙な重さの調整を山登り方でしました．僕の実装だと焼きなましと山登りに差はほとんど見られませんでした．なお，TL が短いので山登りをした際に起こる各 path の暫定的な長さの変更は，ある程度放置してからまとめて更新するとそこそこ良くなりました．
並列処理のシェルスクリプトとかリポジトリとか
リクエストがあったので，載せておきます． xargs と呼ばれるものを使っています．詳しくは man xargs でも叩いてみて欲しいのですが，パイプで受け取った変数を実行する？もので，-P でプロセス数が指定できます．( プロセス数がわからない人は並列数とかと思ってもそんな間違ってないと思います)
GitHub - jupiro/AHC003 の README.md を見ていただけると使い方がわかると思います．何かバグやその他疑問があったら，コメントとか DM とか issue とかで聞いてください．逆になにかアドバイスあれば教えてください
