Topcoder Marathom Match 126 - 論理とか計算機とか数学とか

Topcoder Marathom Match 126 に参加しました。ひさしぶりに MM で非自明なことをした気がする。

概要

グリッド上にいくつかのブロックと穴が配置されている。ブロックには 1 から C までの数値が割り当てられている。ブロックに対して以下の操作ができる。

上下左右に隣接するマスに移動させる。このとき移動先に他のブロックが存在していてはいけない。移動先が穴の場合はその穴に落ちる。
上下左右のいずれかの方向にスライドさせる。ブロックは他のブロックまたは端にぶつかって止まるか、穴に落ちるまで進む。

ブロックが穴に落ちるとブロックの数値-1に係数をかけた値が現在のスコアに加算される。係数は最初はグリッドのマス目の個数で、操作を一回行うごとに 1 減らされる。

方針

一手で100点と二手で200点みたいに一手あたりのスコアが同じだったら、それ以降のスコア係数が大きい状態を保てるので前者を選んだほうがよさそうです。

ということは、なるべく早く落とせるものを落としていったほうがよさそうな気がしたので、そういう感じにしようとしました。

Step 1

まず、いずれかの穴と同じ行または列にあるブロックだけをすべて落とす最適な手順を考えます。これは条件に該当するブロックの数があまり多くないので、短時間の SA でそれなりの解が出ます（たぶん）。

ブロックの並び順で前後関係の制約がたくさん付いたり、複数の穴が落とす候補になるブロックもあって解の表現がそんなに自明ではないのですが、穴と移動方向に番号をつけて「穴 i から見て j 方向にあるブロックを k 個落とす」という形の操作列を解の表現にして焼き鈍しをしました。

ただし、本当に対象のブロックを全部落とそうとすると後ろのほうはあまりスコアの入らのない操作ばかりになることがあるので、後ろの方が割のよくなさそうな列になっていたら適当に切り捨てます。

基準は適当ですが、suffix に対して「その操作列で落とされるブロックの数値-1の総和」を操作列の長さで割ったものを考えて、それが C/5 を下回っていたらその部分はこのステップでは解に含めないことにしました。残ったやつは後で回収されます。

Step2

ここまでで残ったブロックを落とす手順を考えます。ある穴を始点にする L 字のパスを考え、その上にあるいくつかのブロックを落とすことを考えます。例えば以下の二つの 2 のようなブロックを落とす一連の操作をひとまとまりと考えます。

  . O . . . .    . O . . 2 .    . O . . . .    . O . . 2 .    . O . . . .
  . . . . 2 . -> . . . . . . -> . . . . . . -> . . . . . . -> . . . . . .
  . . . . . .    . . . . . .    . . . . . .    . . . . . .    . . . . . .
  . . . . 2 .    . . . . 2 .    . . . . 2 .    . . . . . .    . . . . . .

このような操作を全列挙し、一手あたりの評価値が高いものを選択します。評価値は基本的には落とすブロックの数値-1の総和を手数で割ったものです。正確にはそれをちょっといじった変な式を使っています。手数の少ないものを優先したほうがいいのかなと思ったのですが、試してみた限りは別にそんなこともないようでした。手数を多めにかけてでも深いところにある点数の高いブロックを早めに掘り出してやったほうがいいのかもしれません。

これだけだと計算時間が余っていたので、以下のように別のブロックを一手使って移動させることで他のブロックが効率よく落とせるようなケースに対応しました。

  . . . . 1 .    . . . 1 . .    . . . 1 . .    . . . 1 . .    . . . 1 . .    . . . 1 . .
  . O . . . .    . O . . . .    . O . 3 . .    . O . . . .    . O . 3 . .    . O . . . .
  . . . 3 . . -> . . . 3 . . -> . . . . . . -> . . . . . . -> . . . . . . -> . . . . . .
  . . . . . .    . . . . . .    . . . . . .    . . . . . .    . . . . . .    . . . . . .
  . . . 3 . .    . . . 3 . .    . . . 3 . .    . . . 3 . .    . . . . . .    . . . . . .

  . O . . . .    . O . . . .    . O . 3 . .    . O . . . .    . O . 3 . .    . O . . . .
  . . . 1 . . -> . . . . . 1 -> . . . . . 1 -> . . . . . 1 -> . . . . . 1 -> . . . . . 1
  . . . 3 . .    . . . 3 . .    . . . . . .    . . . . . .    . . . . . .    . . . . . .
  . . . 3 . .    . . . 3 . .    . . . 3 . .    . . . 3 . .    . . . . . .    . . . . . .

現在の盤面から可能な次の手すべてについて、それを行った後で穴から伸びる L 字を全探索してすべて評価して、一番よさそうなものを選ぶようにしました。これがけっこうスコアに貢献しているようです。

ちょっと計算量が大きそうなので高速化が必要だろうと思いながらとりあえず書いたら、わりと何とかなる感じだったので結局高速化はしませんでした。

Step 3

これだけだとまだブロックが残る場合があるので、その場合は各ブロックについて BFS をして最も近い穴を探し、スコアと手数を見てよさそうなものを一つずつ落とすようにしました。この辺はあまり考察ができていません。

この時点で 0 点のブロックが残っているとそれはそのまま放置される評価方法になっているので、0 点に囲まれたブロックは正の点が得られるものも触らずに終了しています。そういうことになるケースはあまり多くなく、スコアへの影響も比較的小さいようですが、たぶん数%ぐらいのケースで発生します。

本当はその場合にも対処しようとしたんですが、対処するとなぜかスコアが大幅に下がり、原因がわからなかったので諦めました（手元で200ケース回したけど問題ないように見える）。