Atcoder Heuristic Constest 002の解き直し
自分のマラソン力向上のために，Atcoder Heuristic Constest 002(AHC002)を解き直した．
そのついでに解説を書きます．
当時参加したときの順位は位でパフォーマンスは
でした．
解き直して，自力で到達できたスコアは
m点で本番順位換算で
位相当，パフォーマンスは
ぐらい？になった．
本番の制限時間である4時間で，ここまでたどり着ける気がしない…
AHC002問題概要
マスの空間に
or
，
の大きさのタイルが敷き詰められている．
- 各マスには点数（
–
）がつけられている．
- 上下左右，隣り合うマスに移動しながら，同じタイルを2度踏むことなく，なるべく多くの点数を集めよ．
- ちゃんとした問題文
解法
初期解を作って，それを焼きなまし．
初期解の作り方
初期解はスタート地点からランダムに進める方向に進んで，進めなくなったら数手巻き戻し，また進める方向に進むという方法を取った． このままだと，局所解から抜け出せないことが多かったので，評価値がしばらく改善されなかったら，スタート地点から計算をやり直しさせた．
初期解の評価関数は（踏んだマスの点数の和） （経路の長さ）
とした．
には特に意味はなく，最終的なスコアが良かったから採用した．
評価関数に経路の長さを加えたのは，後で焼きなますことを考えると，現状のスコアよりも，経路の長さのほうが大切じゃない？とおもったから．
経路長だけで評価することも試してみたが，スコアを含めたほうがスコアは良かった．
この計算をms行って，評価値が一番高いものを初期解とした．
ちなみに，この時点でのスコアはおおよそ
点で，制限時間いっぱい回すと，おおよそ
点になった．
焼きなまし
近傍（遷移先の候補）は現在の経路の一部（長さ –
程度）を壊して，その部分をつなぎ直すことで作った．
経路を壊す長さは時間とともに短くなるようにした．
つなぎ直し方は，壊した長さ分適当に動いて，その後，つなぎ先がある場所へ向けて進む方法を取った．
なので，つなぎ直せることもあれば，つなぎ直せないこともある．
経路を壊して，つなぎ直したときにスコアが改善したら，次はその付近を壊すことにした．
例えば，周りがすでに踏んだタイルによって囲まれていると，壊した部分のつなぎ方が通りしかなく，改善の余地ない．
スコアが改善できなかった場所は行き詰まっている可能性があるので，なるべく他の場所を選びたい．
スコアが改善できた場所はまだ，改善の余地がある可能性が高いので，その付近を壊すことにした．
近傍に遷移するかしないかは，序盤は経路の長さかスコアのどちらかを見て決め，終盤は最終的なスコアのほうが大切なので，スコアのみを見て決めた．
焼きなましの初期温度は，経路をつなぎ直せたときに，遷移する確率が程度になるように決めた．
冷却は実行時間とともに線形に減らした．
非線形な冷却も試してみたが，線形に減らすのが一番スコアが高かった．焼きなまし難しい．
また，しばらく遷移が起きないとき，前回遷移があった温度付近まで加熱するというのを採用した．
これを制限時間いっぱいまでやった．
改善の余地
焼きなましをもう少し高速化したら初期解をパターン用意して，焼きなましできそう．
初期解によっては，焼きなまししてもスコアが伸びないことがあったから，初期解のパターンを増やすと，スコアが安定するはず．
現状で
パターン実行すると，焼きなましの時間が足りないように見える．
焼きなましのときに，経路の端（スタートと反対側の点）は固定したけど，動かしたほうがいい気がする． 気が向いたら実装しようかな？
感想
思ったよりもいいスコアが出たが，やはり時間で実装はできるきがしない．
改めて，上位陣の凄さを感じた．
スコアが安定しない．同じ入力であっても，上振れると
点，下振れると
点になる．
辛い．なんか安定させる方法ないかな？
やはり焼きなまし
回走らせたいな．
焼きなまし技術が高ければスコアが伸びるのかな？
これまでのマラソンコンテストでは気にならなかったけど，ローカルとジャッジサーバーで速度差が意外とあり，なかなか面倒だった．
理由はわからないけど，ローカルではms程度回さないとジャッジサーバーの点数に追いつけない．
m1 macbook airなので，そこまで遅いことはないと思うんだけどな…
Optunaを使ってパラメタを探したけど，なんか微妙． 使い方悪かったのかな？
実行例
余談
記事タイトルの改行のしかたがわからない．"し"が気になる
