Skip to content

モノグサプログラミングコンテスト 2022(AtCoder Heuristic Contest 009)

問題概要

  • 20 * 20 マスのグリッドがあり、外周には壁があり、隣接マスの間には壁があったりなかったりする
  • 左上のあるスタート地点から右下のあるゴール地点に向かって、上下左右(UDLR)からなる命令列に従って移動する
  • しかし、毎ターン「確率 p で命令を無視して何もしない、確率 1-p で指示通りに移動(壁がある場合は移動しない)」という動きをする
  • 200 ターン以下の命令列を作成し、できるだけゴールまでかかるターンの期待値を最小化せよ

時間

240 分

個人的メモ

  • ざっくり「初期解を作って、山登り/焼きなましで改善」
  • 命令列の前の方の変更は後半の状態にまで影響するので、ビームサーチがよさそうに見えるけど、単純な山登り/焼きなましも有効だった模様
    • 良い解の形が「ざっくり全体を右下に持っていった後、散らばった確率値をできるだけ拾う」感じだった？
  • 逆にアドホックなルールとかはあんまり得点に繋がりにくかったっぽい

初期解

  • BFS(01BFS)やダイクストラで最短路
    • 壁にぶつかるまで/曲がるときに+α なコスト。たどり着けない場合は、確率最大マスから最短移動とか、普通の BFS 解を使うとか
  • 貪欲(評価値が一番改善する方向とか)
  • 右下に行きやすくする
  • ビームサーチ
  • 多点スタート
    • iteration 回数が少ないため？か、初期値に依存が強いっぽいので、良い初期解を考えるのではなく、多点スタートも有効だった模様
    • wataさん解

近傍

スコア計算/評価関数

スコア計算の高速化

  • 2 次元配列ではなく 1 次元配列で処理したほうが速い
  • 毎回 1 ターン目から計算する必要はなくて、変更したターンより前は再計算省略できる(定数倍高速化)
    • もし命令列の後半部分の変更が重要ならこの省略はかなり有効そうかも
  • 状態更新を後に持ってくるテク
    • 焼きなまし系の高速化テクで、「状態更新して差分計算後に悪かったら undo する」ではなく、「(状態更新はせずに)近傍の差分計算を O(1)とかで行って良くなる場合だけ状態更新する」テク
    • 基本、不採用になることが多いので、採用時にだけ状態更新することで、高速化できる
    • 今回の場合だと、近傍の差分計算は、前からと後ろからの確率 DP を持っておくと、あるターンの命令が変わったとき、各マスからゴールする確率が後ろからの DP でわかる
      • 差分計算が O(H*W)、更新が O(Turn*H*W)ぐらい
  • ターン順方向更新にすると状態更新時の全ターン更新が不要
    • https://twitter.com/colun/status/1508247782984933377
    • 近傍計算時に変更箇所をランダムに決めた状態更新する場合、変更したターン以降に対して更新する必要があるので、ターン数分かかってしまう
    • 変更箇所の順番をターン順方向に固定すると、後から DP を全ターンで求めておけば、前から順番に計算できるので、更新も O(H*W)ぐらいになる

ビームサーチ

壁にぶつかるまで進む/ダブらせ

p によって戦略を変える

その他

解説

(50 位まで&発言を見つけられた方のみ)