参加しながら考えたこと試したことの源泉かけ流し。

はじめに

5 日目の終わりに完全に方向転換したので、最終的にやったことを読みたい方は 6 日目以降をご覧ください。

1 日目

仕事のお昼休み中に問題を呼んで絶句した。なにこれ。
画像を扱う問題？C++で出れるのかこれ？
と思ったものの、画像の情報はどうやら vector<int> で渡されるらしい。それならまぁ。

MM の 1 日目は環境整備ということで、指定した範囲の seed でテストを走らせた後以下の処理をするスクリプトを書いた。

スコア一覧をクリップボードに貼り付け（Excelに貼り付けて管理するため）
出力画像をアーカイブ

アーカイブはこういう感じ。
f:id:iwashi31:20171007182406p:plain

scores=()

# 問題を解く
for ((i=$1; i <= $2; i++)); do
    score=`java -jar tester.jar -exec "./a" -seed $i | sed -e "s/Score = //g"`
    scores+=($score)
    echo "Case #$i: $score"
done

# スコア一覧をファイル出力
: > score.txt
for score in ${scores[@]}; do
    echo $score >> score.txt
done

# スコア一覧をクリップボードに貼り付け
clip < score.txt

dir=$3
if [ -z $dir ]; then
    dir="default"
fi

if [ ! -e $dir ]; then
    mkdir $dir
fi

# 出力画像をアーカイブ
for ((i=$1; i <= $2; i++)); do
    mv "$i.png" "$dir/$i.png"
done

この後ひとまず画像全体の平均色で塗りつぶすやつを提出してみたけど、4 人中 4 位だった。それはそう。

2 日目

Forum に貼られた gif 動画を見ながらこれでいいじゃんと思った。（これとは…）

多分、ランダムに点を決めて、その周囲の色から塗る色を決めて～みたいな感じなんだろうな。

丸の大きさについては、序盤は大きめの丸、終盤は小さめの丸が使われているように見える。
多分、

大きい丸ばかり → 影響範囲デカすぎてスコアあんまり良くならない
小さい丸ばかり → 画像全体を塗りきれない

ということなんだろう。分からんけど。

色については塗る範囲の平均色で塗ることにしてみる。

で、この画像(seed=8)に対してプログラムを実行してみると、
f:id:iwashi31:20171007184420j:plain

こんな感じに。
f:id:iwashi31:20171007184155p:plain

おぉ、さらっと書いたけどなんとなく目標画像っぽいものが出力されてる。しゅごい…。
この MM、もしかしてめちゃくちゃ楽しいのでは…？

あと一応、円を均等に並べるのも思いついて試してみたけどスコアは低かった。

f:id:iwashi31:20171007190156p:plain

3 日目

色を塗る際、今塗られている色を踏まえつつ、スコアが最大になる色を三分探索で求めるようにしてみる。

f:id:iwashi31:20171007195138p:plain

平均色で塗るより特徴が強く出るようになった。

うーん確かに、今回のスコアって各原色の絶対値の差がそのまま使われる感じなのよね。
だとすれば、平均を取るよりも多数決で決めた方がスコアが高くなるというのはうなずける気がする。

後は円の大きさについてもスコアが良くなるサイズを探索したいところなんだけど、現時点でも最大 12 秒くらいかかってて、定数倍すら危ない状況。
高速化 or 別の戦略…？

色が近いなら徐々に範囲を広げて～みたいなことをやってみたけど、うん、こりゃちょっと厳しそうだね…。

f:id:iwashi31:20171008020119p:plain

4 日目

ランダムに決めた点について、目標と現状の差があまりなければスキップするようにしてみたら少しだけスコアが伸びた。
なるほど、色と半径しか気にしていなかったけど、塗る場所も考慮する必要があるんだなぁ。

いくらか調整してみたりしたけど Forum のやつに遠く及びそうになく挫けそうになる。

Forum のやつ。
f:id:iwashi31:20171008150455p:plain

僕の。
f:id:iwashi31:20171008150528p:plain

コレ見比べるとやっぱり、点の選び方と丸の大きさの決め方が絶妙って感じがする。
波打ち際とかキレーに並んでるもんね。

既存手法に頼ってみるかと「画像丸近似」でググると、画像から円を抽出する Hough 変換なるものが見つかったのでその記事を読む。

う～ん、この手法自体は $O(H^{2}W^{2})$ っぽく見えるのでそのままは使えなそうだけど、代わりにこういうのはどうかなーというのを思いついた。

各点について、そこを中心とするならこのサイズの円にする、というのを事前に計算しておく。
円の内側はだいたいおんなじ色になるよう半径を決める。
その円の大きい順に点を見ていき、目標と現状の差が大きければ円を塗る。差が小さければパス。

1 で結局コケそうな気がしなくもないな…。

(seed=8)
f:id:iwashi31:20171008182151p:plain

ンンーッ、なんか惜しいなァー！
でも建物のシルエットははっきりしてきたし、こういうことなのかなぁ。

パラメータをこねこねしてたら少しスコアが伸びてきた。
橋の欄干部分が良い感じ。

f:id:iwashi31:20171008184504p:plain

この時点で 19位 / 44人、スコア 534418.60。

ここらでテスト用の画像を 20 枚に増やしてみたんだけど、ここで問題点が浮き彫りに。

(seed=12) f:id:iwashi31:20171009013735p:plain

こういうやつね。初期盤面が残るケース。

てわけで、初手で全面を塗りつぶすようにしてみた。

f:id:iwashi31:20171009014647p:plain

まだ出してないけど本番でも多少は伸びるはず。
（むしろ下位にも負けてる可能性が高いケースなので、それなりに伸びて欲しいという期待を持ちつつ。）
→ 13k UP 程度の微増でした。

ちなみに元画像

ここにきて wleite 氏が満点を出した。やっば。

f:id:iwashi31:20171009035937p:plain

5 日目

今は (塗る丸の大きさ, 座標) のペア pair<int, Point> を優先度付きキューに突っ込んで塗る座標の順番を決めてるんだけど、
これだと丸の大きさが同じ座標については x 座標が大きい方から順に出てきてしまい、一つ上の画像みたいに右端に小さい丸が固まってしまうことになる。

小さい丸は出来る限り重ならない方がスコアは良さそうな気がするので、丸の大きさが同じ座標のソート順をランダムにしてみると、微かではあるけど有意にスコアが伸びた。

f:id:iwashi31:20171009182245p:plain

なんか余ってる時間を何かに使えないかなぁ…。
今だと最大ケースでも 10sec くらいしか使ってないので。

3 連休終わりにお風呂に入ってたら新しい解法を思いついた…。

塗る点を 1 つ決める。
その点から周辺を徐々に広がる形で見ていきつつ、各点を 256 色それぞれで塗った場合のスコア変動を蓄積していく。
一番スコア変動が大きかった半径、色で塗る。

多分 $N * (一度に塗るマス数の最大値) * 256 * 3$ ループくらいのはず。
…うーん、ちょっと厳しいか？

6 日目

昨日のアイデアを寝ながら整理した。

ある一点を塗る場合のスコア変動

RGB は独立に考えられるので、例えば R についてのみ注目すると、こういうグラフになる。横軸は 0 ～ 256。

f:id:iwashi31:20171010204442p:plain

複数の点を塗る場合のスコア変動

上のグラフを点の数だけ重ね合わせた形になる。

この重ね合わせについてだが、グラフの形は一定なので、各点でのグラフで傾きが逆転する R 値とその高さ(スコア変動)のみを記憶しておけば、後から $O(\sigma)$ ( $\sigma$ は各原色の色数(=256)) でまとめて復元できる。

この方針でやれば、ある点を中心として円を塗るとき、スコアが最大となる色・半径を $O(r^{2} + r\sigma)$ ( $r$ は調べる半径の最大値(=200くらいで良さそう))で計算できるはず。
（1 項目は各点のグラフの頂点を累積するコスト、2 項目は各半径においてスコアを復元するコスト）

いけるッ…いけるぞッ…！
ウオォォーーーーワイがアルゴリズマーや！！！！！！

朝起きて出勤前にガーッと書いたけどなんかどデカい円しか書かれない。
理論の破綻ではなく単なるバグであることを祈るぞ。

バグだったァーーーーーーーーー！！！！ヤッホーーーー！！！１１

(seed=9) f:id:iwashi31:20171010210516p:plain

Hoooooo!!! スッゲー！！完全に窓やこれ！

しかしまぁ、これでも 540k(27位/55人) なのでみんな何やってんだろなぁ。
もしくは僅差で団子になってるのかな。

スコアがあまり上がりそうにない点、上がらなかった点はパスするようにした。

f:id:iwashi31:20171011001256p:plain

オイオイオイ石像見えてきちゃったよ。

この後もパラメータ調整を繰り返し 620k(22位/58人) まで伸びた。

7 日目

複数個(5～20個くらい)の候補を見繕った後、一番スコア変動の大きい点を選んで塗るようにした。
この戦略は $N$ が小さい場合に特に有効みたい。（数少ない塗るチャンスを最大限有効活用できるので）

(seed=7) f:id:iwashi31:20171011015424p:plain

テントの枠とかの境界線がより綺麗に縁取れているのが見て取れる。

さらに、これやってると制限時間をめいっぱい使えるようになったので良い感じ。

提出すると +80k で 696315.79(17位/59人)！
縮んだスコアの差分は平均 1,400,000 と、数回前の提出時とあまり変わらないんだけど、順位の伸びが良くなってきた。
やっぱり団子になってるのね。

昼休みに適当に弄って Example Tests してたらなんか TLE した。
え、TimeLimit 設定してるんだけどな…。

f:id:iwashi31:20171011212858p:plain

f:id:iwashi31:20171011212912p:plain

い　つ　も　の

& よりも == のが優先順位高いの直感に反するのでほんと勘弁して欲しい。

後から気付いたけど、約 1000 回に 1 回 if 文通すのなら 0x3FF なんだよなぁ。

修正して投げたら 30k 点くらい伸びた。
テストは大事。

後はちまちま改修を加えてスコアを絞り出す。
700k 点台だと平均スコア改善率 1% 程度でも 30k 点くらい上がったりしたのでここは粘りどころだ。

と思ったが、もう全然伸びないし提出ミスも怖いのでこのへんにしておく。

まとめ

ある点を中心として円を塗るとき、スコアが最大となる色・半径を高速に求める方法を考えた。（6 日目の記載を参照）

それ以降は塗る円の中心座標を最適化するため、以下のような細かい改修を行った。

スコア変動が小さい or 小さそうな点はパスする。
- 中心点の色が目標の色に十分に近ければパス。
- 直近 5 ターンのスコア変動の和 / 15 を下回るスコア変動の点はパス。
- 最適な半径が 10 未満の点はパス。
一つの点を塗る前に 5～20 箇所の候補について計算しておき、一番スコア変動が大きかった点を塗る。
- スコア変動が 2 番目に大きかった点は次ターンの候補に残しておく。
上記の処理は時間制限が近づいてきたら適当に端折る。

今回の MM は、自分の持てるアルゴリズム力・考察力を活かせた感があるので大満足。
黄色に復帰できると期待しているぞ！