問題概要

www.topcoder.com

1 日目

問題を読む。シンプルでいいね。

まず連結成分で思い出すのは、「連結成分の最小化」≒「色の異なる隣接要素の数の最小化」と置き換えても良い感じに評価ができるということ。前者より後者の方が差分計算がしやすい等のメリットがあるので、焼き鈍しをするなら後者をベースに考えたほうが良さそう。ただ後者だけだと条件を満たせたか否か、つまり連結成分を C 個にできたか否かが判断できないので、最終的には連結成分をちゃんとチェックしてあげる必要がある点は注意。

ただ今回の出力内容って操作の列なので、うまく焼き鈍しがハマるかは分からない。途中の操作を変えると後の操作に影響があるから。蓋を開けてみればそういう問題もプロは焼き鈍してたりするんだけど、あまり自分がうまくいった記憶はないし、うまくいくイメージもない。

まずは貪欲を考えてみる。例えば、目標とする盤面を決め打ちして、その状態へ持っていくまでの最小手数は厳密に求まるのだろうか？もし十分高速にそれが計算可能なら、いろんな目標盤面に対してそれを試すという手が考えられる。

僕の直感だと、例えば C=4 のケースなんかを考えると、最適解は四隅から各色の固まりが生えてるみたいな感じではなく、なんかこう、アメーバみたいな感じのが絡み合ってるみたいな感じになりそうな気がするんだよな。でも焼き鈍しとか、目標盤面を作るにしても、前者の解に寄りがちになりそうな気がしていて…これはまぁ心に留めておくくらいでいいか。

冷静に考えたら、目標盤面の作成では手順は気にしなくていいんだから焼き鈍しが可能なんですよね。ただどのような手順で目標盤面へ持っていくかは全く考慮しないから、どのくらい少ない手順で達成できそうかの評価は難しそう。

こないだ連結成分の数最小化する問題あったよな〜と思って MM118 を見返しにいったけどあまり参考になりそうな感じではなかった。

とりあえず初手としては、目標盤面を作ってその状態へ持っていく貪欲を試してみようか。考えポイントとしては、

どういう目標盤面を作るか
どのような手順で目標盤面へ持っていくか

という 2 点に分解できる。あとおまけとして、目標盤面への手順を計算した上で、目標盤面を微調整して手順が減ったりしないか試してみることもできそう。それはまた後で。

ひとまず 1. は上の方から順に色を詰めていく感じ、2. も同じく上から貪欲に詰めていく感じで実装して valid な解はできた。後は目標盤面を色々試して一番良かった解を選ぶやつかな。

今の目標盤面は上から詰めてボーダーっぽい配色になってるけど、これってつまり、例えば上に青を固めるとなると、下の方にある青も全部上に掻き集めないといけない。なので、目標盤面は各色が全体に行き渡ってるようなパターンが嬉しい気がする。

じゃあ渦巻か？盤面上を一筆書きするパスが得られればそれに沿って順に色を配置していけば valid な目標盤面は簡単に生成できて、これを渦巻状の一筆書きパスに対して適用すれば良い。渦巻だと盤面の上下左右に各色が配置されるので、それぞれ近くにある色を取ってくれば良くてうまくいきそう。

後は色の順番や渦巻の向きをランダムにして生成した色々な目標盤面に対して、先ほどと同じ上から詰める貪欲解法を適用してやる。実行してみると単発ボーダーと比べると平均 40% くらいの手数が削減されている。いいね！

まだ結構無駄のある解法というか、そもそも方針が合ってるかの自信もあまりないのでびくびくしながら初提出してみたが、開始 6 時間後の時点では相対スコアでほぼ 100 点のスコアが得られた。やっぱりみんな苦戦してるのね。

ビジュアライザ、-delay 0 つけたときに初期盤面から動いてくれなくてクッソ不便だな…、と思ってたけど -na オプションつけてアンチエイリアシング切ったら -delay 1 で眺めれるくらいには高速になったのでこれで良いことにする。

さて、次は目標盤面へ持っていく手順の最適化だ。今はただ単に上から順に詰めてるので、これを四隅から、一番近くの目標色セルとの距離が最も小さいセルを優先して詰めるようにしてみる。これで一応 10% 弱くらい改善した。

ただビジュアライザを見てると特に終盤に無駄な動きが多い…。そこをちょちょいとすれば連結成分数最小の条件は満たせるのに、目標盤面を厳密に再現するためごっそり動かすみたいなことをしていてもどかしい。状況を見つつ目標盤面を修正するみたいなことをした方が良い？

あと、どの丸をどこに運ぶかは二部マッチングなので、最小費用流に落とし込めると思う。これは試してみても良さそうかな。

渦の外側の色から順に最小費用流で二部マッチングして配置していくのを実装して 12% ほど改善した。Yay!

2 日目

丸を目的地に運ぶ際、x 座標優先で合わせた後 y 座標を合わせるような移動の仕方で固定だったので、ランダムにジグザグ進むようにした。1.6% の改善。

二部マッチング実装する過程で目標盤面をランダムに回転させる処理を一旦消してたのを復活させたのと、あと N が小さい場合には渦以外のパターンも試すようにした。3.6% の改善。

もし C = 2 なら櫛を噛み合せたような目標盤面が良さそうだな〜と思いつつ、この問題は C > 2 なので仕方なく渦書いてたんだけど、色を順番に配置していって最後の二色になった後は C = 2 の問題になるのよね。そう考えると、渦の中央だけは櫛を噛み合わせるなりした方が嬉しいかもしれない。

実装してみたらスコアの伸び縮みはまちまちだったけど、N > 23 のケースでは平均で見て改善してそうだったのでそれらにだけ適用することにした。全体で見ると 1.3% の改善。

N が大きいかつ C が小さいケースでスコアが大きく伸びた（画像は seed = 4）

丸を目的地にジグザグ運ぶ際、可能なら目的盤面と色が一致していない方向を選ぶようにしてみた。が、スコアは伸びず。このあたりはランダム性に身を任せた方が良いらしい。

各色が盤面全体をカバーするようなパターンについて思いを馳せる。パッと思いつくのは 4 本の線で渦を巻くようなパターンなんだけど、微妙な個数の違いを連結性は担保しつつ調整するのがめんどくさそう…。でも今までの感じからすると実現できれば伸びそうなんだよな。頑張ってみるか。

その前に、今の色ごとに二部マッチングして順に配置していくやり方だと、入り組んだ連結成分を配置して fix しちゃうと他の要素が動かしにくくなるので、このやり方を変えてあげる必要がありそう。最初に全色二部マッチングしておいて上から順に配置していくとか？うまくいくかなあ。

順位表を張ってたら wleite さんが提出した後 5 点くらいスコアが下がった。ただ wleite さん自身は 80 点程度に留まっていて、つまり特定のケースにめっぽう強い解法なのかな？N が小さいケース or C が小さいケース…？

3 日目

4 本の線で渦を巻くようなパターン、帳尻を合わせる実装が重い…。ただ帳尻さえ合わせれば C = 4 のケースでスコア 40% くらい改善するのは確認してるので、モチベーションしかない。

（ここから時間に追われてメモを残す余裕がなかったのでコミットログから拾える情報だけ列挙します。）

1:19 - 4本線での渦巻実装完了。実験をして、C==4 かつ N>=14 のときのみ適用。
2:27 - 二部マッチングで決めた割当を配置する途中で眺めて、入れ替えると距離の和が改善する場合に目的地を入れ替えるようにした。
- 二部マッチングの割当はあくまで配置開始前の最適解であり、配置開始後にかき混ぜられると最適でなくなるので。
2:51 - 盤面をランダムに反転させるように。
3:22 - C==6 の場合も 4 本線の渦巻パターンを使うように。
5:30 - C==8 の場合も 4 本線の渦巻パターンを使うように。
7:27 - 配置を進める途中に目標盤面を修正した方が手数が少なくなる場面にでくわしたら目標盤面を修正するように。
7:59 - 二部マッチングをする際、距離が遠い点は絶対にマッチさせないようにしたら何故かスコアが伸びた。
11:50 - 生成直後の目標盤面に、色を交換可能な二点をランダムに置換する処理を追加。
- 盤面の多様性を増やすことでよりベストな解に出会えるようにするため。
18:09 - 制限時間のラスト 20% くらいはそれまでのベスト解での目標盤面を微調整したものでひたすらトライするように。