MM143 TreeMaker 参加記
問題
戦略
- 完成図の作成を行う
- 色の配置を決める
- タイルの配置を決める
- 初期解の作成
- 枝の追加・削除による木の変形
- 完成図に対してもとのタイルとのどのタイルが対応するのかを割り当てる
- 盤面を操作してタイルを揃える
- y軸を揃える
- x軸を揃える
完成図の作成
ただ闇雲に盤面をスライドさせても最小全域木の完成は難しいので、先に完成図を作成するところから始めました。
色の配置を決める
色の配置については各色について領域の4隅 [0, 0], [N - 1, 0], [N - 1, N - 1], [0, N - 1] を起点としてそこから dy, dx の最大値が小さい順にセルを彩色していきました。（なるべく正方形になるような配色になります）
もう 1つのパターンとしてシンプルに順番通りに彩色していくパターンも用意います。
タイルの配置を決める
初期解法の作成
まずは最初にベースとなる最小全域木の作成を行います。幸いテスターに木の作成方法は書かれていたので今回はそれを利用しました。
最初に対象の色の領域に空のタイルを設置します。
その後、ランダムにタイルとランダムな方向を選択して、その方向にまだタイルが設置されていない場合は枝を伸ばします。
この処理を未完了の領域が無くなるまで繰り返します。
木が完成したら他の色に対しても同様の処理を行っていきます。
枝の追加・削除による変形
木の性質として「辺を 1本追加すると必ず閉路が出来る」というものがあります。そしてまたその閉路の中の 1本を辺を消すことで再度木になるので、この特徴を利用して木の変形処理を行っていきます。
辺を追加して閉路の検出を行う（計算量は N * N)
見つけた閉路の中から辺を 1つ削除する。
この処理を行うことで木を維持しつつ使用するタイルの種類を変更することが可能となります。今回はこの処理を繰り返しつつ元の盤面のタイルの種類の数との差分が小さくなるように変更を行いました。
タイルの割当を行う
完成した盤面に対して元の盤面のタイルをどの位置に割り当てるのかを決定します。AHC011 の時は最小費用流を用いて割当を行いましたが、今回は速度重視で貪欲に割当を行いました。割当の評価としてはこの後に「y軸を揃える」-> 「x軸を揃える」という作業を行うので y軸が等しいものが多くなるように評価を行うようにしています。
盤面を操作してタイルを揃える
盤面を揃えるパートについては「y軸を揃える」 -> 「x軸を揃える」の順番で行っていきます。
y軸を揃える
現在持っている余剰パネルを正しい y軸の方向に入れます。余剰パネルが完成版で使用しないパネルの場合はまだ完成していない y軸で適当な箇所に入れます。
x軸を揃える
x軸を揃えて行きますがその際に「余剰タイルを含めた行の連結成分が 1になるように盤面の操作」を行っていきます。
例として下記の画像を使用します。
まず、本来そのタイルがいるべき x座標に対して有向辺を張ります。現状では連結成分数は 3となります。
この数が 1になるように行を横にスライドさせたりタイルの形が一緒の場合は値のスワップ等を行います。
あとは元の場所にタイルを押し出すことで x軸を揃えることが出来るようになります。
ソート後
このように x軸をそろえつつ行を1つ上に押し上げることが出来ます。この作業を N 回繰り返すことで盤面を完成させます。
まとめ
AHC011 と似たような問題ではあり実際に完成図を作るところは完全に AHC011 の方針と一緒だったが、盤面を完成させるパートが完全に別物でそこをどうやって手数を短くするのかを考えるのは楽しかった。横軸を揃える -> 縦軸を揃える方法だと多くの手数を使ってしまうのでそこをなんとか改善したかったが最後まで何も出来なかった。（上位勢と近い考察はしていたがうまく動か無さそうだなと案を捨ててしまったのが良くなかった）
