今までゆるふわで参加していたAHCですが、今回は（当社比で）がっつり気合を入れて挑みました。
（当社比で）結果も上々だったし、何より問題が面白かったです。
第-1世代
多くの人がまずは実装するであろう、まっすぐいって一回だけ曲がる、を私も実装しました。
意気揚々と最初の提出をしたところ、燦然と輝くWAがｗ
単にscoreの入力を受け取るのを忘れていました。てへ。
第0世代
気を取り直して、scoreの入力を受け取るようにして提出。みんな大好き63,179,310,956点を得ました。
ここから本格的にスタートです。
第1世代
考えたこと
- 最初はなんの情報もない
- 受け取ったscoreを元にアップデートする必要がある
やったこと
とりあえず、最初は全ての辺を5000とおきます。BFS*1をして最短経路を取得し、返ってきたscoreと最短経路の距離を比較し、scoreが大きければ仮においた辺の長さが足りてないことになるので伸ばす、逆なら短くする、を繰り返します。
具体的には「仮の長さ（最初は5000）」 *= score / 「計測した長さ」をします。
これで91,292,668,752点になりました。いきなり900億台に突入して暫定14位で順位表1ページ目に入ってしまい、テンションも上がります。
うおー、順位表1ページ目に入った！！#AHC003 pic.twitter.com/kySEXvILh9
— Toy (@mdstoy) 2021年5月22日
まあここがピークだったんですけどね！
第1.5世代
考えたこと
辺を通った回数や、scoreが高めに出たか低めに出たかの回数を数えて、辺の重み付けに利用しようとかしていたようですが、うまく行かず伸び悩んでいました。
統計とか機械学習の素養があればここでいろいろできるんでしょうけど、ないものはしょうがないです。
第2世代
考えたこと
- スコアは後半に行くほど重みがある
- 前半は辺の長さの計測に専念させたほうが得できるのでは？
- 辺の長さは、辺単位で完全なランダムではなく、行単位列単位で重み付けがされている
- 計測すべきは（辺単位よりも）行/列単位の損得なのでは
やったこと
序盤は、第0世代のロジックを復活させて、行/列単位で計測することとします。これで、BFS時の精度が目に見えて上がり、スコアも930台に迫ります。
ビジュアライザで追いかけていくと、結構最善に近いパスを通っているケースが増えていて感動していましたｗ
第2.5世代
やったこと
ここからは何をやってもほとんど伸びませんでした・・・。一応成果が少しでもあったものを羅列すると
- なんかよくわからんけど
score / actualで得られた比率に適当な係数を食わせる- 有意な差は出るんですが、根拠はわからず
- 序盤の行/列単位の計測時、実際に通っていない辺についても行/列単位で長さを変化させるように
- 微差ですが、やらないよりはましレベル
- 単にBFSをすると、誤って計測していたとき誤りを増幅させてしまうので、焼きなまし的なことをして必ずしも最短経路を取らずに遊びをもたせるように
- 後半の精度は少し上がったような気がしますが、大幅な改善には至らず
できなかったこと
一方、やりたかったけどできなかったりうまく行かなかったことは
- 全ての行/列をうまく網羅できなかったため、得する行/列が5000のままだと、最後まで放置されてしまう
- 無理やり通るように仕向けてもスコアが落ちてしまった
- 感想TLを見ていると、初期コストを5000より低く設定すれば、一度はそっちに通せるっぽいですねーなるほど
- 通った回数や高低どちらに出たかをうまく補正に使う
- これはアイデアとしては初期からあったものの、具体的にどう落とせばいいのかは最後まで解決せず
これら（特にひとつ目）が解決すると結構伸びそうな手応えはあったんですが・・・。
結果
というわけで、暫定スコア93,315,231,887点の暫定168位、システムテスト後の最終スコア2,806,411,894,424、最終順位160位でした。
001が772位、002が550位だったので、今回は大健闘といってもいいのでは？！
感想
終了直後の感想TL眺めてると、そもそも考察が甘い部分が多々あって（M=1, 2の違いとか全然考えてなかったり）まだまだやなーと思い知らされたりもしました。無駄を減らして考察をより深めるために、次回以降は複数テストケースを自動的にぶん回せる仕組みとか、効果的なデバッグログを出すとかそういうところにも注力していきたいかなと思ってます。Rustの勉強ちゃんとしないとなー。
あと、最初に「（当社比で）がっつり気合を入れて挑みました。」と言ってはみたものの、数学的に高度な考察ができないのは、これはもう仕方がないので。仕方がないので。今後も凡人にできる範囲で楽しめたらいいなーと思ってます。今回ももちろん楽しめました！！ありがとうございました。お疲れ様でした。
