Skip to content

AtCoder Heuristic Contest 050

問題概要

  • N*N(=40*40)のマス目からなるスケートリングがある
  • 初期状態ではM個のマスに岩が置かれている
  • 1体のロボットを使って、以下のゲームを行う
    • 岩のないマスすべて(N^2 - Mマス)について、岩を置いていく順番を決める
    • 岩のないマスからランダムに1マスが選ばれロボットが置かれる
    • ここから、すべてのマスに岩が置かれるまで以下を繰り返す
      • ターンiでは、ロボットは現在位置から4方向をランダムに決めて岩にぶつかるかスケートリングの端まで滑り、その後、決めておいたi番目のマスに岩を置く
      • もし、ターン終了後にロボットが潰されたらそこで終了し、潰れなかったら1円獲得して次のターンに進む
  • 最終的に獲得賞金の期待値ができるだけ高くなるような岩の置く順番を求めよ

時間

  • 4 時間

個人的メモ

スコアの計算

  • 各ターンでの得られる賞金の期待値は、あるマスの期待値が「そのマスにロボットがいる確率prob * 1円」なので、それを全マスでの合計したものになる
    • 最終的に獲得できる賞金の期待値は、全ターンの賞金の期待値の合計
  • ビジュアライザでいうと、岩を置く(黒マスにする)とそこのマスにあったprobが0になってしまうので、「できるだけprobの高い(赤い)マスを潰さないように岩を置いていけ」という感じ
    • ビジュアライザの下の線グラフでいうと、AUC(線の下にくる部分の面積)ができるだけ大きくなるようにしたい
      • 理想的には、ターンの最後の方までほぼ1.0を維持して、最後にガクッと下がる感じにできるとよい
      • これは「途中はほぼprob0のマスしか潰さず、最後に少数のprobが高いマスを潰す」ような動きになるはず
  • テスター・ビジュアライザなどにスコア計算式があるので、参考にできる

スコア計算の高速化

  • 単純に、「各マスについて、4方向の移動先マスを見つけて、現在のマスの確率の1 / 4を配布」とすると、移動先のマスを見つけるのにO(N)かかるので、各ターンでO( N^3 )、全体でO( N^5 )の計算量になる
    • N=40なので結構厳しく、10回程度ぐらいしか試せない
  • これは高速化が可能で、あるマスの移動先マスは、そのマスの間にあるマスもその移動先マスになるので、累積しながら走査することで、各ターンO( N^2 )、全体でO( N^4 )で求められる

probの変化

  • 「例を見る」などで観察してみると、ターンが進むごとにマスのprobが減ったり増えたりしていることがわかり、いくつか考察できる
  • 連結成分ごとに独立
    • 岩によって領域が分断されてしまうと、ロボットの行き来ができないので、それぞれ独立になる
    • もし、領域内のprobの合計がほぼ0なら、その領域のマスはどの順番につぶしてもあまり関係ない
  • probが高いマス、低いマス
    • 岩が隣接していないマスは、ロボットが止まれないので、probは0になる
    • また、岩が隣接している場合でも、領域内のprob合計が低ければprobは低い
    • ロボットが止まるのは岩にぶつかるかスケートリングの端なので、そこはprobが高くなりやすいはずだが、一方で、岩が隣接していてもprobが低いマスはいくつも存在している
      • 直線やL字、四角形領域などの角の部分が高くなりやすいのはわかる
  • probが減っていくマス、増えていくマス
    • probが減っていくマスというのは、そのマスへ来る確率よりも出ていく確率の方が大きいマスで、probが増えていくマスはその逆
    • たとえば、4近傍のうち3つが潰されているマスの場合は、3 / 4で留まり、1 / 4は出ていくが、それ以上が入ってくると増えていくことになる
    • 岩を置くことで、経路が変化し、probの増減の仕方も変化する(させられる)

probの誘導

  • 減っていくマスと増えていくマスがあり、うまく配置を作れると、少数のマスにprobをまとめることができる
  • 基本的には、溜まって外に出ていかないようなsinkマスを作れるとそこに集まるので、それができるのを目指す
    • 最上位には、いくつもそういうのができないようにすることも必要

アプローチ

評価関数設計して貪欲

  • 各ターンで、「どこのマスに置くか」を、評価関数を設計して、貪欲に選ぶようにする
    • 最初に「probが低いマスから埋めてったらどうか？」とかが考えやすいので、そこからの発展で考えやすい
    • だいたいは時間が余るので、微小な乱数を入れる or 上位n件をランダムに選ぶようにしたり、後半を局所改善する、などもできる
  • 評価関数には、以下の要素などを組み込んで適当に重み付け
  • 対象のマスのprob
    • そもそもprobが高いマスは選びたくない
    • ある程度小さいprobは0として扱う、など
  • 通過が多いマスを潰さない、通路を塞がない
    • そのマスを通過しているprobが多いところは、そのマスを潰すことで、その隣接マスに溜まる(probが高いマスが増える)ことになるので、それを避ける
    • (「直線を残す」効果も)
  • くぼみ(隣接で1箇所だけ空いている状態)を作る、隣接4マスの状態を考慮
    • 隣接が1箇所だけ空いているマスは、probのうち3 / 4がそこにとどまるので、そこに溜まりやすい
      • 他のマスにprobが散るよりも、くぼみのマスに集中しやすくなる
    • くぼみができるように、隣接マスを考慮して岩を置く
  • 連結成分を増やさない
    • 連結成分が増えてしまうと分離してしまうので、それを避けるために、できるだけ連結成分が増えないマスを優先する
      • 厳密ではなく、隣接8マス判定とかでも
  • 直線を残す
    • 岩がないマスが直線のようになっていると、「1ターンで長距離移動しやすい」「その両端マスに溜まりやすくなる」などよさそうなことが多そうに思われる
      • (解説放送) あまり良くない形である市松模様的なのが避けられる効果がある
    • 直線を残すようにしたり、行・列に重み付けしてタイブレーカーを導入するなどすると良い模様
    • 直線が最後に残ったとき、1マス飛ばしで埋めていってほしいが、適当に評価関数を書いているとそのようになってくれたりもする(なってくれないときは2マス先に岩があるとき加点など)

n手後の盤面状態(定常状態)を評価値にして貪欲

  • n手後のマスの盤面がどうなっているか？をシミュレーションして、それを評価値にする
    • 岩は置かず、そのままほっといたときの状態(定常状態)
    • nは10とか
  • 全候補マスでやるのは計算量的に厳しいので、probが低い何マスかだけ試す(10マスだけとか)で十分な模様
  • 評価値は、probができるだけ少ないマスに偏るとうれしいので、分散やエントロピー、各マスのx乗(x=2とか10とか)の合計、とかを用いるとよいみたい

T字を作成してprobを誘導

  • https://x.com/chokudai/status/1941862619125788692
  • 「T字型」は、両端マスに入ったprobが外に出ていかなくなる(一方通行)ので、他のマスからprobを集める効果がある
  • そのようなマスを用意してターンが進むとそこに集まるので、うまく塞がないように埋めていく
  • これを極めると、「T字の溜まる部分が3マスになるような形」にprobをほぼすべて集約することができるようで、ほぼ理論値が達成できる(延長戦、解説放送)

置く順番を局所改善

その他

小さいNで試す

  • 問題の制約ではNは固定だったが、ビジュアライザだとNを変更(「fix N」のところ)して生成させることができるようになっていて、小さいNにしてmanual modeで試す、ということができた
    • N=40だと大きいが、N=10ぐらいだと考えやすい

理論値

勇者のくせに生意気だ

お絵かき

解説

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