Topcoder Marathon Match 117 参加記

はじめに

2020/04/23 ~ 2020/04/30に行われたMM117の参加記です．時間を割いて参加できたのでやったことなどを残したいと思います．

問題概要

www.topcoder.com

2次元ルービックキューブのような問題です．問題文に貼られていたGIF画像が非常に直感的でわかりやすかった．

任意サイズの正方形マスを回転させることができ，各マスが本来あるべき場所に近いほど ペナルティが少なくなります．回転させるのにもサイズに応じたペナルティが課されるので， できるだけ少ない回転ペナルティで完成形に近いものを作ることができれば高得点となります．

やったこと

回転させる操作の順番を入れ替えると大きく状態が変わるので，ヒューリスティックに解くならビームサーチ(以下BS)が良さそうというのが第1印象でしたが， グリッドサイズが最大4040なので，この盤面情報を常に持ちながらBSをするとあまりビーム幅などが出せません．

雑な図ですが，赤色部分の回転探索を行うときに青色部分の情報はあまり重要そうではなさそうなので，必要最低限の情報を 持ちながらBSを行えば擬似的に4040のBSを再現できそうと考えました． 具体的には，ざっくりと77のブロックに盤面を分け，各ブロック内でBSを行うという感じです

各ブロックは少しずつ重ねることで，本来あるべきブロックへの「輸送」もできるようにしました．

BSの行い方ですが，各ブロック内での最適配置になるまでBSを行う -> 次のブロックで最適配置になるまでBSを行う -> etc... という方法ではあまりスコアが伸びませんでした．おそらくですが，最初から最適配置にしてしまうと，後から輸送されてきたブロックを配置するとき，最適な配置を一度崩す->輸送されてきたものを配置する という無駄な動作が発生してしまうからだと思います． 最終的に自分の出したコードでは，各ブロック内でのBSを並列に少しずつ進めていくという感じにしました．

BSの評価関数ですが，「本来のペナルティ + Σマスの目的地までの距離のk乗」を採用しました．kはPに応じて変わる係数です(?)． 前述の理由より，最適配置のブロックに後からマスを埋め込むのは余分なコストがかかってしまうため， 各マスが本来あるべきブロックへ早く輸送できるようにするため，このような形になっています．

以上をいい感じに実装するとこんな感じで動きます．(seed値は3)

MM117
最終的にはこんな感じになった(意味不明)
1: 12
2: 17416
3: 813
4: 32
5: 4493
6: 449
7: 8876
8: 6450
9: 61
10: 3331 pic.twitter.com/U4VCFiWobQ

— たこし (@takoshiiiiiiiii) 2020年4月30日

結果

provisinal 順位: 20位, 相対スコア: 71.80061

各シード値ごとのスコア

1. 12
2. 17416
3. 813
4. 32
5. 4493
6. 449
7. 8876
8. 6450
9. 61
10. 3331

Psyhoさんがぶっちぎって強すぎる...

BSのやり方がよくないのか，

上図のように，ひとつずれてしまう構図が散見されました．これを解消できたらもっとスコア伸ばせそうですが，解消方法がよくわからず...