MM128参加記

MM128に参加しました。

今回はTCO21 Regionalsの一環として開催されていて、いつもと桁違いの賞金が用意されてましたが、日本を含む東アジア地区は層が厚すぎてねぇ…。

一日目

英語でさっぱりわからない開会式のあと、MM128の問題が公開されました。N*NのグリッドのC種類の色のボールを隣同士スワップで各色４近傍でつながるようにするための手数を最小化せよ、といった感じ。ビジュアライザが動くのでテンション上がります（単純）。あとMMでは久々にインタラクティブじゃない問題でした（よね？）。今回は７２時間しかないので、手っ取り早く正の点数を取る方法を、と思ったのですが、ちょっと思いつかなかったのでとりあえず寝ました。

二日目

ディレクトリ掘って、ダウンロードするものダウンロードして、シンプル過ぎるサンプルコード眺めておしまい。

三日目

各列縦にソートとか試してみたけど、運がいいケースでしか正の点数にならないので、腹をくくってコード書くことにしました。

まずは上からつづら折りにボールを並べた状態を最終形として、上から順番にそろえていきました。

これで２６点くらい。

四日目

並べる様子を眺めてると右のを左にもっていったり左のを右にもっていったり無駄が多い気がしたので、色別に縦にならべて上から揃えてみました。

これで４２点くらい。

この後、移動するボールを探すのに上から走査線式に探索してたのをBFSで最短距離のボールを探すようにしたり、四隅から揃えたりしてみましたが、さほど改善せず。上から揃えていたのを上と下から交互に揃えるようにしたら少し良くなったりしました。

なんかもう何も思いつかない気がしていたのですが、子供の習い事の送迎でパソコンを離れていると、気が付いたことがありました。上の図で言えば、青いボールは全体に散らばっていたのを全部左に寄せているのですが、４連結でさえあればむしろグリッドに広がっている形の方が移動距離が少ないのでは？でもそれぞれの色が４連結で、でも広がっているってどんな形？グリッドのサイズや色数によらず４連結が保証される配置にするにはどうしたらいい？あれこれ考えた結果中心から２本の渦巻きが伸びる形にしてみました。

これで５７点。アイデアをせっせとコーディングしたらグッとスコアが伸びて、これぞマラソンの醍醐味って感じ。この後、色の並べる順番をnext_permutationで順次試して、一番スコアのいいのを出力するようにしたら６６点程になりました。まだ終了まで時間はありましたが、今度こそ、もうアイデア尽きたぞということで、家族とホタルを見に釧路湿原へ行ってきました。子供たちも夏休みだしね。

提出締め切った時点で暫定１８位。渦巻き直ぐに思いついた方多かったようですね。

結局今回も焼きなましやビームサーチどころか山登りもせずに終わってしまいましたが、BFSやnext_permutationなどアルゴの知識が生かせて面白かったです。あと、日本、層厚すぎ。