参加しながら考えたこと試したことの源泉かけ流し。
問題概要
2 次元グリッド上に自走掃除機とゴミが落ちている。掃除機は自分の担当のゴミを最短距離で回収する。掃除機の移動距離の総和ができるだけ大きくなるよう壁を配置せよ。
全文はこちら。
1 日目
問題を読む。二次元グリッド上での迷路長最大化…？
これ見たことあるな！？
第2回 RCO日本橋ハーフマラソン 本戦 : A - ぐるぐる庭園
Aの input-1.txt の出力を動画で (10088点) #rco_procon pic.twitter.com/uLwVdfPFle
— yowa (@yowa) March 10, 2018
オンサイトで悔しい思いをしたのでよく覚えている。当時僕は斜めジグザグを思いつけず、縦横のジグザグを作って上位争いから外れてしまった。少し問題設定は違うけど、あのときのノウハウがある分だいぶ優位に立ててるんじゃないかな。
とりあえず様子見で、上図左のようなジグザグループを作った後、どこか 1 セルを埋めて長い一本道を作ってみる。埋めるセルは全部試して一番スコアが高かったところ。これを提出した頃には c7c7 さんがほぼ満点でトップに君臨していて、僕のスコアは 60 点ちょい。過去問に似てたから勝ちを確信してたけど流石にそんなに甘くはないか。
ジグザグを左右反転させたやつも答えの候補として試すようにしておく。
このジグザグ戦法は盤面が掃除機とゴミでぎゅうぎゅうの時に弱い（壁が突き破られて迷路長が短くなるので）。これらのケースには別のアルゴリズムを検討する必要がありそう。
パッと思いついたのは、「壁から 1 セル空けたところから反対に向かってまっすぐ壁を引く」を全通り試して、スコアが最大になるやつを採用していく山登り。山を登りきったら空セルからなる長方形を探して、ジグザグで埋める。
適当に乱数を組み込んでタイブレークの選択に幅を持たせ、時間いっぱい回す。これと斜めジグザグを両方試して良かったほうを採用するのを提出して 69 点。
2 日目
wleite 氏によりビジュアライザにマニュアル操作機能が追加される。控えめに言って神。
今のジグザグは、盤面を二分割する斜め線上にオブジェクトが被ってしまうと迷路長がかなり短くなってしまう。これを少しでも回避するため、ジグザグのバリエーションとして縦や横に 1~2 セルずらしたものを追加してみる。これは少し効いて 74 点。
3 日目
上の seed = 2 の図を見ると分かる通り、掃除機が一切通らず無駄になってる空セルが結構残っている。これを何とか有効活用してあげたい。
マニュアル操作で遊んでいると、いくつか簡単な変更でスコアを伸ばせるパターンが見えてきた。
ジグザグを作った後掃除機が通らないセルは壁で埋めて、上記パターン（回転・反転含む）等を見つけたら置換してあげることにする。これで 80 点。
4 日目
よくよく考えると、中央付近でジグザグの折返しが接している箇所の境目は自由に動かすことができる。
例えば上図で左下の道の方が右上の道よりたくさん掃除機が通過しているとすると、当然境目を右上にずらして左下側の道を伸ばしたほうがスコアが高くなる。昨日のパターン置換の処理をする前に、この境目最適化を（適当に貪欲に）行うことにする。83 点。
5 日目
何も思いつかないので小さい盤面用貪欲の乱数を適当に弄ってみる。あまり期待はしてなかったけど一応誤差くらい伸びて順位がひとつ上がった（だから何？）。
6 日目
本当にアイデアが尽きたのでこの記事を書き始める。
1 日目の「斜め vs 縦横ジグザグ」画像を作っていると、 N = 20 では迷路長に思っていたほど差がないことに気付く。これ小さい盤面では縦横ジグザグも試した方が良いのでは？
う〜ん、やっぱり行き詰まったときはブログ書くに限るな。
実装してみたけど伸びなかった…。縦横ジグザグは壁の割合高いからオブジェクトと被りやすいのかな？
7 日目
最終日なので色んなシード値で走らせて -1 が出ないか確認しておく。
そしてついに wleite 氏が c7c7 さんを抜いて 1 位に！勝負の行方は…！
おわり
例によって後半全然スコアを伸ばせなかった…。
どうやらぐるぐる庭園解法は罠だったらしい？
最初ぐるぐる庭園に引きずられて斜めベースで初期解作っていたけど、それは罠だった
— tomerun (@tomerun) August 5, 2020
他にも焼き鈍し案がちらほら。確かに小さいケースだとそっちの方が賢そうに思える。
5 日目くらいからは明らかに限界を感じていたので、がっつり方向転換した方が良かったのかもしれないな。
