Skip to content

AtCoder Heuristic Contest 042

問題概要

  • 20*20マスのグリッド上に、40個の福と40個の鬼の駒が置いてある
  • 1回の操作でどこかの行または列に対し、左右または上下に1マスだけずらすことができる
  • 操作によって盤面の外に移動する場合、盤面から取り除かれる
  • できるだけ少ない操作回数で、福を1つも取り除くことなく、鬼をすべて取り除くような操作列を答えよ

時間

  • 4 時間

個人的メモ

サンプルの操作の無駄を改善

  • サンプルは「各鬼について、福がいない方向に向かって外に押し出して、その逆操作して元に戻す」をしている
  • 逆操作をしない場合、各鬼について「福がいない方向がある」というのを満たせなくなってしまう
  • とはいえ、完全に元に戻さなくても「各鬼について福がいない方向がある」を満たせていればよいので、それを満たすところまで逆操作すれば十分なため、操作の無駄を減らすことができる

福をどかしながら鬼を押し出す

  • 「福がいない方向」ではなく、「端に近い方向」向かって動かすと外に出すまでの操作回数を減らせる可能性がある
  • ただ、福がいる可能性があるため、その福をどかしつつ押し出すことを考える必要がある
    • 基本的には、鬼を右に動かしたい場合、そのライン上の福は上下に動かせば1手でどかすことができる
  • しかし、これをルールで書こうとすると、福が連続していたり、端に福がいて動かせなかったり、複雑な形状になってルールが複雑化してしまいうる
    • BFSで手順を求めたり、詰む場合は諦めてビームサーチで多様性を確保しつつ操作列を求めることはできる
  • また、これだけだと上位に入るには操作回数的にまだ不十分

鬼を「まとめて押し出す」

  • ある鬼を、外に押し出すライン上、または、ラインに近い他の鬼をライン上に移動してまとめて押し出し操作をすると、別々に外に押し出すよりも少ない操作回数で押し出せる可能性がある
    • ある鬼を押し出すときに、他の鬼をまとめて動かせるので、操作回数が減る
  • これがかなり効果的で、積極的に狙うことで操作回数が減らせる

アプローチ

「近くの鬼をまとめて押し出す」操作を1手として探索

  • 「近くの鬼をまとめて押し出す」操作を1手として、鬼の順番(や押し出す方向)をいろいろ試す
    • 乱択だったり、後ろに足していくビームサーチ、特定の行・列にまとめる、など

操作列を焼き鈍す

  • 操作列を状態として、「ある操作を続けて外に出せる鬼を全部外に出す操作」や「上下左右へのN手分の移動操作」などを近傍に焼き鈍す
  • 文脈が弱い(ある部分を変えても他の部分への影響があまり大きくない)ので、操作列の局所改善が有効
    • ただ上記の1つ目の近傍が重要そう？

過去改変型

  • 操作列を状態とするが、後ろに「周囲の鬼をまとめて押し出す操作」を追加するのではなく、「鬼を外に押し出す」や「上下左右へのN手分の移動操作」などを操作列の途中に**挿入**する貪欲やビームサーチ
    • 過去改変型
    • 上記の焼きなましのイメージに近い
  • 「鬼をまとめて押し出す」操作は、ルールで書かなくても、構造的には「ある鬼を外に押し出す」＋「押し出すライン上に他の鬼を持ってくる」ような感じになっており、「ライン上に鬼を持ってくる操作」を近傍に追加することで、探索に組み込むことができる
  • 評価関数
    • 各マスの外側までの距離を持つような2次元配列を用意して、操作列を逆から逆方向に動かすようにすると、ある時点から最後までその操作をしたときに「そのマスは外に出るか？」や「あるマスは最終的に外側まで距離はどれぐらいか？」などが求められるので、福を落とさずに、その評価値ができるだけ小さくなるのを目指す
# イメージ
(外側までの距離を持つ2次元配列)
1111111
1222221
1233321
1234321
1233321
1222221
1111111

「(U,0) -> (R,1)」という操作列の場合、

(R,1) # 2行目をL方向に動かす
1111111
2222210
1233321
1234321
1233321
1222221
1111111

↓

(U,0) # 1列目をD方向に動かす
0111111
1222210
2233321
1234321
1233321
1222221
1111111

的なイメージ。
(0のマスは最終的に外に出ているマスで、それ以外は外までの距離)

その他

操作の種類数

  • 1手あたりだと、操作は「どの行/列か」と「上下/左右」しかないので、40*2=80通り程度しかない

seed=0のベスト解

解説

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