Skip to content

第二回マスターズ選手権-予選-

問題概要

  • N*Nマスの盤面があり、マスには鉱石(1種類or3種類)か岩、または鉱石に対応した穴がある
    • 初期位置は1種類目の穴
  • 操作として、各ターンでは、4近傍への移動、4近傍への運搬、4方向へぶつかるまで転がす、ができる
  • できるだけ少ないターン数で、鉱石をすべて対応する穴に落としたい
  • 問題は以下の性質の違いがある
    • 問題A: 鉱石は1種類で、鉱石と岩がまばらに散らばっている
    • 問題B: 鉱石は3種類で、岩は存在しない
    • 問題C: 鉱石は1種類で、岩が多い

時間

  • 360 分

個人的メモ

「転がす」

  • 「転がす」と、長距離移動ができるので、これを活用できると手数が大きく減らせる
    • ただし、1つ転がした後、それを追いかけるように移動してしまうと、運搬するのと変わらない
    • 近くの鉱石を複数転がす→追いかける、のようにすると、1つずつ運ぶよりも移動回数を減らせる
  • さらに、うまく他の鉱石や岩を配置しておくと、転がりすぎてしまうのが抑えられる可能性がある

一部の岩を鉱石として考える

  • 邪魔な一部の岩を鉱石として考えると、いろいろ考えやすかったり、実装を省略できる可能性がある

穴の上下左右方向はあけておく

  • 穴の上下左右方向をすべてあけておくと、そこまで移動したらそこから転がせば1手で入れられる
  • 岩も鉱石とみなして穴にいれておく

すべての鉱石が連結になるように岩を鉱石とみなす

  • 問題Cでは、岩が多く、岩を動かさないと鉱石をすべて運ぶことができない
  • あらかじめすべての鉱石にたどり着けるように一部の岩を鉱石とみなしておくようにしておくことで、少なくとも近くから貪欲に穴に運べばすべて運ぶことができる
    • 問題Aでも、岩に囲まれて運び出せない場合は岩を動かす手順がないと詰むので、そういうのを回避できる

アプローチ

  • 問題の性質が違うが、結構似たアプローチでも対応可能だった模様

一旦全部を上下左右どこかに寄せる

  • 雰囲気的に、穴に近い方向に「転がす」を使ってよせると、鉱石が固まっているので、穴までの距離が減ってよさそうな気がする
  • しかし、基本的には、20*20=400ターン以下を使ってよせて、20ターン以下で移動して、そこから穴に入れていく、という感じになるため、無駄を削っても結構ターンを使うため、ハズレなアプローチだった

鉱石を1つずつ穴に運ぶ

  • 各鉱石を「転がして入れられるところまで運んで、転がす」のを繰り返すことで1つずつ穴に入れられる
    • 穴の上下左右のラインをすべて開けておけば、そのラインまでの移動で済むので結構移動距離が減る可能性がある
  • どの鉱石の順番で運ぶかだったり、穴じゃなくてもうまく転がすことを考えると、より改善ができる
  • 貪欲、ビームサーチ、乱択、など

評価関数を作って貪欲、ビームサーチ

  • 盤面の評価関数を考えると、「鉱石や岩の数」「穴までの距離」「プレイヤーの位置に鉱石か岩があるか」などの要素を組み合わせたものが考えられる
    • 貪欲でプレイアウトしたものを評価値とするなども
  • うまく、評価関数が小さくなるように、ビームサーチなどで操作を求められる
    • どの鉱石を選ぶか(基本は一番近くのもの)、鉱石を1つずつ穴に運ぶまでの操作列の1手目や途中までや転がした場合を1回の操作にする、などいろいろ考えられる
    • 重複盤面の除外はしておかないと無限ループする可能性もある

鉱石・岩の訪問順を焼きなまし

その他

「穴までの距離」にチェビシェフ距離を加える

  • max(dy,dx)に小さい重みをかけたものを距離に加えると、距離が同じになってしまうところに傾斜がつけられる

類題

解説

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