Topcoder Marathon StainedGlass - びったんびったん

https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=17394&pm=15264

Example Tests

It's good that I ran several times only seed 2

1, 188798.4375, 120831.0, 5/20
2, 2.0110236926112E7, 1.8450842E7, 44/1000
3, 2.585656663217272E7, 2.4089131E7, 20/555
4, 7493222.916638096, 6457431.0, 40/518
5, 4.1234232157296196E7, 3.9425575E7, 22/970
6, 8907273.54193523, 8194529.0, 31/728
7, 9728903.343749998, 8059686.0, 15/152
8, 2.7994073349021245E7, 2.5841511E7, 12/294
9, 6883570.201690821, 5904721.0, 44/552
10, 2.3159190600224324E7, 2.1495614E7, 18/474

1, 188798.4375, 120831.0, 5/20 f:id:hakomof:20190115103509p:plain

2, 2.0110236926112E7, 1.8450842E7, 44/1000 f:id:hakomof:20190115103600p:plain

3, 2.585656663217272E7, 2.4089131E7, 20/555 f:id:hakomof:20190115103646p:plain

4, 7493222.916638096, 6457431.0, 40/518 f:id:hakomof:20190115103715p:plain

5, 4.1234232157296196E7, 3.9425575E7, 22/970 f:id:hakomof:20190115103808p:plain

6, 8907273.54193523, 8194529.0, 31/728 f:id:hakomof:20190115103831p:plain

7, 9728903.343749998, 8059686.0, 15/152 f:id:hakomof:20190115103857p:plain

8, 2.7994073349021245E7, 2.5841511E7, 12/294 f:id:hakomof:20190115103946p:plain

9, 6883570.201690821, 5904721.0, 44/552 f:id:hakomof:20190115104009p:plain

10, 2.3159190600224324E7, 2.1495614E7, 18/474 f:id:hakomof:20190115103500p:plain

方針

序中終盤ともに 1 母点を周囲 8 マスに動かす焼きなまし（輪郭追跡 + BFS で差分計算）

試行回数は 125 万くらい

初期状態はランダム
序盤 4 秒
- 画像を辺の長さが 1/8 になるよう縮小
- N 色
- 定期的に減色を空撃ちして、隣接領域との色差が小さい母点らや、同色で至近にある母点の片方らすべてを一度に、色差が大きそうなとこに飛ばす
中盤 12 秒
- 画像は原寸大
- N 色
中盤と終盤の間
- 色数を黄金分割探索、 kmeans++ で減色
終盤 4 秒
- 画像は原寸大
- N の 2%-10% 色

考察の流れ

だいたい時系列

焼けそうなので焼く。

色

状態は

母点の座標
母点のグループ
グループの色

からなる。このうち母点の座標・母点のグループが決まれば最適なグループの色は求まる。差の絶対値和の最小なので中央値。なので、母点の座標と母点のグループを焼きなましてグループの色は差分更新で最適値に追従させる。関連記事

具体的には、色素値ごとの面積の BIT と色素値和の BIT を持つと追加・削除・最適色でのスコアなどが O(log(256)) になり差分更新できる。

近傍

母点の自由な移動はうまく差分計算できても O(領域面積 * log(256)) で遅い。もっと速くしたい。近傍を小さくしよう。母点を周囲 8 マスに動かせば領域の境界しか変わらない。

動かす母点の輪郭を輪郭追跡で求めて queue に入れる。 px の所属する母点が変わったか調べて、変わっていたら周囲 8 マスを queue に入れる。 queue が空になるまで BFS する。これでほぼ厳密に差分計算ができた¹。

近傍が小さすぎない？

この問題のように要素同士に区別がない（母点を入れ替えてもスコアが変わらない）とき近傍は大きくなくてよい。なぜなら、遠くに動かす近傍は、母点を玉突きのように少しずつ押し出しても代替できるので。

HACK TO THE FUTURE 2018予選山型足し算も同様の理由で近傍が小さい。

近傍が小さすぎない？ 2

近傍は大きくなくてよいけど、小さいほどよいわけではない。画像最大 800px に対して 1px の移動は小さすぎる気がする。でも近傍を大きくすると遅くなってしまう。じゃあ画像を縮小しよう。 800px に対する 1px の移動よりも 400px に対する 1px の移動は相対的に大きい。画像を縮小すると速くなるので一石二鳥。

さらに、画像を縮小して焼いてから原寸大で焼くと試行回数と精度のバランスが取れるが、大きい近傍で焼いてから小さい近傍で焼くことにもなる。近傍をだんだん小さくするのは良い工夫なので二石四鳥。

減色

疲れたので以降雑

母点のクラスタリングは基本的にうまく焼きなませない。例えば、空のグラデーションが 5 色のとき 4 色のグラデだとか 6 色のグラデへの移行は全体的にずれるので焼きなましの小さな近傍では対応できない。なので、母点の座標の焼きなましと母点のクラスタリングは分けて最適化することにする。やり方は序盤に減色だとか、終盤に減色だとか、徐々に減色していくとか色々考えられ一概に判断できなかったので全部試した。結果、序中盤は N 色で、1 回だけ減色するが良かった。結果から考察すると、一度減色してしまうと同じ色同士の母点が結びついて動きづらくなるのでギリギリまで減色しないのが良いようだ。

クラスタリングは kmeans++ 。といっても厳密スコアによる山登りに等しい。代表色のクラスタリングではなく領域の全色集合同士のクラスタリング。クラスタ数は黄金分割探索で、凸じゃないけどだいたい凸ってことで気にしない。黄金分割探索で求まったクラスタ数±1に kmeans++ を数百回多スタート。これ大事。さっき書いた通り近傍探索（焼きなましとか kmeans++）がうまくいかないので多スタートで誤魔化している。というか多スタートする必要があったから母点の座標の焼きなましと母点のクラスタリングを分けた。