モノグサ プログラミングコンテスト2022（AtCoder Heuristic Contest 009）に参加しました。
結果は39位でした。
問題
やったこと
移動を少しづつ変える焼きなまし
初期解
- 氷上滑り（壁にぶつかるまで進む）を繰り返してゴールまでたどりつく経路
- ゴール側からダイクストラみたいな計算をして、曲がる回数が少ない経路を求め、200回の移動になるように移動をだぶらせた。
- 上記でゴールできないケースでは、存在確率最大の場所からゴールに進む、を繰り返して経路を決めた
近傍
- 移動を1個削除
- 移動を1個ランダムな方向で追加
- 移動を1個選んで2回移動したことにする
ビジュアライザ
seed 0 ：氷上滑りでゴールできる
seed 2 ：氷上滑りでゴールできるが物忘れ激しい
seed 8 ：氷上滑りでゴールできない
コンテスト中考えたこと
コンテスト前は焼きなましのライブラリを整備してて、焼きなまし問題どんとこい！だった。
問題を読んでこれは焼きなましではないなと思った。（移動経路の自由度が高いから？）
ビジュアライザで手動操作してみると、壁に何度も進むことで1か所に確率を集められる。氷の上をすべってゴールまで進むみたいなパズルを解いて、壁に何度か進むようにしたらいいんじゃないかなあ。
それでゴールに到達できないケースあるかな？テストケース生成方法見たらわかるかもと思って壁の生成方法を見たけど変な記号いっぱいでてきて理解できない。
大体ゴールできるでしょと思って実装～提出。100ケース中33ケースでゴールに到達できない。この時点で100分経過。残り140分（絶望）
あかんこれじゃ全然だめだ。ゴールに到達できないケースをどうにかしないといけない。ゴールに到達できるケースも壁に何回進むかの部分を調整する必要があるので、時間あまりかけられないか。
ぱっと思いついたのが、その時点で存在確率が最大の場所からゴール方向に移動するを繰り返す。これを実装してローカルで実行したら悲しいくらい点数が出ない。とりあえず提出。
4,076,306,178点 残り80分 183位
氷上滑りでゴールにたどり着けないケースのスコアがあまりにも低すぎるので何とかしないといけないが、残り時間そんなにないしこの時点で解法決まってないのやばいよね。もうダメだあ。
新しい解法はたぶん思いついても実装する時間無さそうなので、焼きなましを入れて少しでもスコアを上げよう。あでもスコア計算ってどうやるんだろう？問題文を見ても理解できないし、いろいろ試したけどスコアが全然一致しない。うわーん。
公式テスターのコードをみて何とかスコアを計算できるようになった。しかしもう残り30分しかない。
移動経路を1個削除するという近傍だけで焼きなましをやってみた。スコアかなり上がるじゃん。
6,007,009,650点 残り25分 135位
移動経路追加と移動経路をだぶらせる近傍を追加して提出
6,972,408,352点 残り20分 39位
えーなんでこんなにスコアあがるの？考察してる時間もないし、あとは高速化とパラメータ調整ぐらいしかできなさそう。
コンテスト終了
最終スコア 7,016,045,541点 39位
反省・感想
氷上滑りで大体ゴールできるでしょ思って実装して確認するとこに時間かかりすぎて良くなかった。
スコア計算方法理解するのに時間をかけすぎた。問題文見てもわからないならテスターのコード見たほうが早いね。
焼きなましでスコア上がるのがまだ理解できてないから考察しないと。ビームサーチ系も良いらしいけど評価値どうするんだろう。
氷上滑りできないケースはほぼ探索任せになってる。貪欲でもスコア取れるようにならないといけないなあ。
焼きなましはライブラリ整備してたおかげで実装早くできたのは良かった。
