モノグサ プログラミングコンテスト2022(AHC009)に参加しました。
問題はRobust Memory of Commuting Routes。
割合で移動する人をゴールまで移動する問題です。
提出799人中704位でした。
問題
割合で移動する人をゴールまで移動させてね。*1
P(0.1～0.5)の割合で移動せずにその場に留まるよ。
考察
余分に壁にぶつかれば移動し損ねた人が追い付いてくる。
スライド移動すれば良さそう。
やったこと
ビームサーチとスライド経路探索の間で反復横跳びしていました。
ビームサーチは初動は良さそうだけど途中から反復横跳びしてしまう。
あとは纏まらずに薄くなってしまうので、薄さにペナルティを付けたりと評価関数に調整が必要そう。
スライド移動はビームサーチで時間を削ってしまったので、これ時間内に仕上がらないなぁ…という感じ。
結局提出できるか怪しい状態なので、正の点である最短ルートの移動をちょっとだけ伸ばしたものを出して終了。*2
その後手直ししたらビームサーチは最低限動いたけど、本当に最低限なので調整はたくさんしないと駄目そう。
他の人の解法を見て
焼き鈍しが強そう？
ビームにしろ、スライド移動で割合を纏めることを主眼に置いて探索単位を変えるなりした方が伸びそう。
スライド移動は遠回りになることも多いので、1マス単位で探索するビームだとかなり深くする必要がありそうで、つまり多様性を上手く保つ調整と高速化が必要そう。もしくは少量を高速にゴールさせる方針か。
感想
確率というか割合を使う問題でありながら運要素も無く、楽しそうな問題でした。拡張ダイクストラ慣れしていない＋何かにはまって大ロスしたのもあって、4時間では全然足りなかった。8時間～長期でやりたかった…。
あとは下手にレートが上がってしまったうえに非減少レーティングなので、レートが上がる見込みが無いと全然気持ちが入らないっぽい。短期は水パフォ出れば御の字だろうし、長期も1ページ目は苦しいような問題も多いだろうから、向き合い方を見直さないといけないかも。
