■ [MM] Marathon Match 95 CirclesMix 
https://community.topcoder.com/longcontest/?module=ViewStandings&rd=16959
1日目（木曜）
問題を読んだ
2日目（金曜）
テスターをカスタマイズ（いつもの）
- マルチスレッドでのバッチテスト
- 結果の出力を良い感じに
- 問題パラメタを自分で指定できるようにする
3日目（土曜）
テスト画像をwikimediaからクロール
（イラストとか本のページとかの画像は弾くのだけど、基準に主観が入るので迷うのが多かった）
1000枚取ってきたけどそんなに要らなかったかな…
greedyに円を一つずつ置いていくのを実装
- ランダムな位置・半径で円をたくさん作る
- すでに生成したものと近すぎる円は生成されないようにする
- 半径は徐々に小さくする
- それぞれの円に対して、最適な色にしたときにペナルティがどれだけ減るかを評価
- ペナルティ減少が一番大きい円を選ぶ
- 選ばれたやつと重なるもの以外の円は保持しておいて再利用する
また、選んだ円に対して、位置と半径を動かす山登りを実装
4日目（日曜）
高速化色々、SSEも使う
円の最適な色を決めるために、円の内部のピクセルに対して中央値を取る処理が重いので、かわりに円の中心にある7*7の正方形範囲の中央値を使う、という大胆な近似を取り入れたり
最終的に、greedyフェーズでは各ターンで 10000/sqrt(N) 個の円を生成し、選ばれた円に 10000/sqrt(N) イテレーションの山登りを行った。所要時間は6,7秒くらい？
5日目（月曜）
まだまだ高速化
円を置いてしまった後に、時間いっぱい使って繰り返し山登りで改善するのを実装（高速化を頑張っていたのは、これをやる時間を作るため）
山登り対象になる円をランダムに選ぶと、評価のためにその円の上に重なっている円をすべて再描画しないといけなくなって受け入れられないほど遅そうで、そうならないよう1つめの円から順番にひとつずつ山登りした。
各ピクセルごとに、未来側に円が何枚重なっているかと色の和を覚えておけば、再描画無しで評価できる。
- まずN枚目〜2枚目までの情報を計算して、それを使って1枚目の円を山登りする
- 未来側の情報から2枚目の円の寄与分を取り除いて、2枚目の円を山登りする
- 以下同様
この問題は、とにかくいかに逐次改善可能な形に持って行くかが勝負だと思ったので、ここが一番の重要ポイントだった
6日目（火曜）
調整色々
前日実装したものが山登りになっていなかった（良い解になっても状態を更新しておらず、初期状態の近傍しか調べてなかった）という致命的なバグを修正
7日目（水曜）
パラメタ調整やる、が、ほとんど変わらず
AWSで36coreマシン借りて35スレッドでテストを実行したら、めちゃくちゃ遅くなってまともにテストできなかった。16スレッドに減らすと普通だったので、コア数もったいないがそれで。
原因は追ってないけど、テスターで画像を読んでるからだろうか？
やらなかったこと
- はじめは画像を縮小して処理することで高速化
- やったけど良くならなかった
- 画像から円をパターン検出
- seed=1を見るとそういうことを考えてしまいたくなるが、実装も実行もコスト高過ぎそうでやめた
結果
- 暫定スコア 983939.39
- 暫定順位 2位
- 最終スコア 982939.39
- 最終順位 2位
- レーティング 2491->2541
- 生成画像 https://www.dropbox.com/sh/anef2l81rch03lx/AAD-D9HVWa4cnB1ifbJ4-1gIa?dl=0
1位とだいぶ差があった。
最終日にしか提出しなかったのは、戦略のつもりではなくて、単に何度も提出するのがめんどいからです
