メモを公開します 解説向きではないです

大きい塊を1色or2色 作る。接続は木。

焼きなまし法をやった。 いらないコンピューターを1ターンで消せる など、性質の良い状態でプランを立てることと、 そのプランを実際に操作に起こすのの2段階になった。

ただし、プランを操作に起こしたときにプランの回数より実際の行動回数が大きくなるのは日常茶飯事なので、 焼きなましの時間の後半で、 約1000回焼きなましのループをするたびにプランを操作に起こすのを行い、 回数のずれを焼きなましにフィードバックする方式で行った。

焼きなまし法について

遷移は、
・木に頂点を加える (a → a-b)
・木から頂点を外す(a-b → a)
・木の辺の間に頂点を入れる(a-b →a-c-b)
・その操作の逆 (a-c-b → a-b)
・木の辺を選び、 上下左右にずらす
でやった。

この「プラン」はコストが単純化されていて、
・動かした頂点に対して、移動距離+その間にある他のコンピューターの数(斜めに動かす場合は最小になるようにとる)
・接続として使う部分に対して、邪魔なコンピューターの数
・接続の数 の和だけでとりあえず計算する。

たまに、 そのプランに対してそれを実際に操作になおし、 暫定コストとどのくらいずれているかを算出して、 焼きなましにフィードバックする。

実際に操作するところ

どういう木を作るかきめたら、それを実現する。 フローを使う、

この場所に木に使わないコンピューターを置いていいかどうかのマップを作る。(木に使わないコンピューターは互いに区別しなくてOK)

その後、フローにおいて超頂点S,Tを用意して、 そこに木に使わないコンピューターがあるならS->頂点 (容量1,コスト0) 隣り合う頂点同士かつ、そこに木に使うコンピューターがないなら、 頂点どうしを繋ぐ(容量無限、コスト1) その頂点に木に使わないコンピューターを置いていいなら頂点->T(容量1,コスト0) のフローを用意して、 最小費用流を流す。

すると、隣り合う頂点の場所において、 いくつ木に使わないコンピューターを移動すればいいかわかるから、 その通りに動かす。

(最小費用流の制約より、きちんとフローが流せていれば動かし方は適当に貪欲にやってOK)

邪魔なコンピューターを動かせたら、 必要なコンピューターをせっとする。

工夫点

1色と2色を考える 2色でやるとき、画面全体にうまくやるために、初期解を作る

AAAAAAAAAA
.A.B.A.B.A.B.A.B
.A.B.A.B.A.B.A.B
.A.B.A.B.A.B.A.B
.A.B.A.B.A.B.A.B
.A.B.A.B.A.B.A.B
BBBBBBBBBBB

ただし、「A」と書いてある部分は、 交わる部分はコンピューターの種類Aが必要、 交わらない部分は任意 という意味である。Bも同じ。