トヨタ自動車 プログラミングコンテスト2022（AHC015）に参加しました。
問題名はHalloween Candy。グリッド上でランダム湧きする飴をスライドさせる問題でした。
結果は提出807人中198位でした。
問題
10*10のグリッドに飴が1つずつ置かれるよ。
飴の種類(全3種類)は100回分事前に分かってるけど場所はランダムだよ。
飴が置かれる度に盤面全体を傾けてスライドさせて、巨大な連結成分を作ってね。
考察
うーんこれはIS-MCTS。
偏らせれば良さそうなのは分かるけど、偏らせる方法が分からん。
実装
やりました。
高速化しようとSIMDに手を出したら遅くなったので、最低限やっただけになりました。
IS-MCTSはRustでMCTSを書くときついでにやろうかなと先送りにしていたのですが、短期コンで出てくるとは…。書いたことないどころか理解しきってもいないものを短期コン中に作り始めるのはクレイジーですが、なんとかなりました。
でもそもそも完全に理解していないので、本当に出来ているのか分かっていません。いずれ再調査しないと…。
他の人の解法を見て
1手先に湧く飴に合わせて動くのが良かったらしい。
シミュレータで言えば、Nターンで打ち切るのがいいとか、プレイアウトにルールベースを仕込むといいとかは、いつものモンテカルロ法のお話。この辺は問題の性質も考察しないと組み込みにくいですね…。
