simanのブログ

ゆるふわプログラマー。競技プログラミングやってます。Ruby好き

MM 123 Jewels 参加録

参加してました。最初から最後まで順位表の不具合で自分の正しい順位がよくわからなかった。(恐らく 4, 5 位あたり)

https://www.topcoder.com/challenges/b846362a-218e-4a3d-b86c-3d38f472e199

方針

スコアの計算式が「ラインスコア * コンボ数」で計算されており、ラインスコアは (x - 2) ^ 2 で指数的に増加するので、なるべく長いラインを複数消すのが重要。

長さ N のライン消しパターンの作成

自分は盤面サイズごとに長さ N のラインを消すためのパターンを用意して、それを利用して連鎖を組んでました。

N = 8

f:id:simanman:20210206050404p:plain:w300

N = 16

f:id:simanman:20210206050429p:plain:w400

また、何列同時消しを行うかによってブロックを追加しています。(下の画像は 3列同時消しを行う場合)

f:id:simanman:20210208211844p:plain:w400

連鎖型の作成

インスコアを稼いだ後はコンボを稼ぐことで高スコアにつながるので、連鎖系も各盤面ごとに用意しました。

N = 8

f:id:simanman:20210206050539p:plain:w300

パターンの組み合わせで盤面構築

スコア取得のパターンと連鎖のパターンを組み合わせて、作成した盤面の構築を行います。 スコアのパターンについては、同時消しの数によってブロックを追加で上積みしています。

f:id:simanman:20210206051149p:plain:w500

同時消しの数が増えるほどスコアも増えますが、現状の盤面の色状況によっては作成出来ない盤面を構築することになるので、その場合は構築できる盤面の中で最大の同時消しが出来るような盤面の構築を行っています。

自分の場合ほとんどケースで「同時消しの数: 1」が構築可能になるようにパターンを作成しました。一番作りにくいケースが「N: 8, C: 10」でしたが、このケースでもほとんど問題にならないようにしてます。(どうしても作れない場合は 1手貪欲に探索して適当にブロックを消してました)

構築した盤面の配色

盤面を構築した後は各ブロックの配色を決めていきます。自分は「現状の盤面から最小手数で達成出来る盤面」を選択するように配色を行いました。配色に関しては焼きなましで配色パターンを探索しています。

発火処理

配色が完了したら、後は実際に目的の盤面までの手順を作成して発火します。パターンは決め打ちだったので発火箇所も決め打ちです。 後は「盤面構築 -> 発火」の繰り返しをゲームが終了するまで繰り返します。

感想

スコア計算的に「Nライン同時消し + 連鎖」にたどり着かないとそもそもスタートラインに立てない感じだったので、早めに気づけたのは良かった。後半は「暴発を防ぐ」ための戦略を色々考えていたが、解決策を最後まで実装出来なかったのでそこが反省点。

「これ焼きなましだ!」みたいな感じの問題でなければ良問という風潮がある(偏見)