# 2022/03/26～4時間　AHC009(モノグサ)

https://atcoder.jp/contests/ahc009
## コンテスト

### 感触
グリッド問題。
上下左右に移動してある地点からある地点まで行く。
移動順序を確率的に忘れてもたどり着ける文字列を生成するのが目的。

> 途中でオフィスに到着した場合はその時点で移動を終了する。

とあるので、前のお掃除ロボットに近いかもしれない。

> 200 以下の文字列

というのがちょっと厄介かも。

startが左上(0以上4以下の座標)、endが右下(15以上19以下)となっているので、適当に右下に行けば悪くない。
右下に行った後、上手く戻る文字列を作るとか？

忘れる確率が10～50%。

Maxが250,000×400 = 100,000,000(100M)
適当に手動でやって75,389,875(75M)
となると80M代の勝負か。

壁に擦り付ける事で、ほとんどの確率を収束させられる。
seed=0で手動80.6M、83文字。
seed=1はいじわるで62M
seed=2はもっといじわる。20M

ただ、ざっくり近くなるようにやっても似たような点は出る。
seed=0で手動84M出た。
引っかかるポイントを適度に脱しつつ、徐々にゴールに近づくでいいっぽい。

### 方針
１．ゴールから直線上の経路を伸ばしていき、スタートまで到達する最短マスを出す。
２．上手いこと集団を形成して、壁に擦りつけて削りながらすすむ。

２．でいく。
ゴールからのマスを評価値として、できるだけ評価が高くなるように貪欲で動く。
制限時間が2秒なので余った時間の使い道で勝負がある？

[1:40経過]
貪欲を組んだ。seed=0で82,988,956。やったね。
ただ、seed=1だと18,752,687。かなり範囲を広げてしまう。
ビムサをすれば回避するか？
とりあえず袋小路の評価を落とす。
→seed=0が84Mになったのでちょっと上がった。
が、seed=1が16M。
１．とのハイブリッドがいいかも。
ビムサは辞める。
[2:50経過]
１．できた。seed=1で54M(54,330,388)
ちゃんとスコア計算してベストを求める。
[3:20経過]
できた。1.2.を切り替えてベストを出す。
時間が200msしか使ってない。
２．の方針を2手読みする？
[3:30経過]
雑なコードで4手読みにした。
まぁまぁ上がる。時間的には5手もできるけど、効果が微妙だった。

順位表、74Mがトップ。
提出で64Mで88位。ちょっとしょぼい。

素直にビーム打つか、１．の方針で最寄りまで近づいたあとにビームかなぁ。
ちょっと数字変えて65Mフィニッシュ。100位以下。

## 感想戦
TERRYさんが最後まくって１位。

https://twitter.com/terry_u16/status/1507660599001780226

他にも焼いている人がちらほら。
だいたいビームでちゃんとやると70M、焼くと73Mみたいな感じっぽい。
いい感じの本筋を見つけた後、溢れてしまうやつらを焼いてなるべく多く拾っていくゲームなので、焼くのが強かったっぽい。
多点スタート(というか本筋をちょっとずつ変化させる)ことが重要で、辺の重みランダムが効いてそう。