MM92 考えたこと
問題文 https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16857&pm=14485
MMの方針
— hakomo (@hakomof) 2017年1月19日
誤差ゼロの焼きなましをひたすら高速化。
近傍はライトを１つ動かす。
最後に極近傍山登りで微調整（こちらも誤差ゼロ）
試行回数は１５万回～３５０万回
感想
CutTheRootsに高速化焼きなましって意味で似てるなー、CutTheRootsってたしか最上位厳密スコア求めてるんだよなーこれも厳密スコアかなーで突っ走った結果、近似スコアだったでござる。 初日で方針ミスって、しかも下手に良いスコアとってしまい方針ミスに気付けなかったので次からは気をつけたい。
自分の方針だと色んな箇所に色んな高速化をしていて高速化ゲー（もちろん高速化だけでは厳しいけど）としてはかなり楽しい（そして練習になる）問題だと思いました。（ただこの記事ではほとんど省略されてます）
焼きなまし
近傍はライトを１つ動かす。 焼きなまし序盤はライトを大きく動かして、終盤は小さく動かす。動かす距離は時間の経過とともに指数的に小さくした（試行回数の少なさを補うにはこれが良いと思った）。
壁の近くはすぐにライトがカットされるので良い位置ではないだろうと遷移しないようにしてみたがあまり効果なし。
遷移先に偏りのない605Kでるプログラムでinner_xとinner_y（小数点以下の座標）の分布を見ると、ものっそい偏ってた。
ヒートマップの色はテキトーだけど光源の45%がinner_x == 0 || inner_y == 0だった。おそらくライトの半径が整数で壁も整数刻みなので、inner_x == 0 || inner_y == 0だと壁と壁の間にすっぽりぴったし収まりやすいのだと思われる。なのでinner_x == 0 || inner_y == 0に遷移しやすくしてみたのだけどあまり効果なし（がーん）。
山登り
CutTheRootsしかりTerrainCrossingしかり座標が広い問題は最後に極端に狭い近傍で山登りというのをみなさまやってらっしゃる。のでライトを１つ周囲8dotに動かす山登りを最後にした。
高速化
100dot x 100dot（１セル）をunsigned long long[100][2]の格ビットで表現する。
放射光のビットパターンと円形の光のビットパターンのandビット演算をすれば１つのライトのビットパターンが求まる。ライトとライトのorビット演算をすればライトが重なったビットパターンが求まる。あとはビットの数を数えれば（__builtin_popcountll）厳密なスコアが求まる。
円形の光のビットパターンは事前に計算して持ってくる。
放射光のビットパターンは、 まず、放射光の境界線の角度が、光源から外に向かって貰うＤＰで求まる。 次に、境界線の角度と光源の座標から境界線の直線の式が求まる。 そして、直線の式に求めたいビット列のy座標を代入すれば何ビット目から何ビット目まで立ってるかがわかるのでビット列を求める。
他の（でも重要な）高速化
あるセルをあるライトが完全に照らしているとき、他のライトの処理の省略、代替、遅延、枝刈による高速化（これが重要だけど説明できず）。
壁による遮蔽なしライトの重なりなしなセルのスコアは２次元累積和でO(1)で求まる。
差分計算もしてます（これも重要だけど説明できず）。
