AtCoder Heuristic Contest 001 解法メモ
最終スコア(システムテスト後)は980,823,067,375点で95位でした。
自明解の生成
広告の希望(x, y, r)に対して、長方形( (x, y), (x+1, y+1) )は解の条件を満たす
スコア計算
- 解の条件を満たしているかを判定する
- 満たしていれば、各広告についての点数の和を取って全体のスコアを算出する
基本方針
山登り法、乱数の値の幅を徐々に小さくする
1点探索 (resize_1way)
広告を一つランダムに選択する 任意の方向に適当な大きさ伸ばし/縮めることを試す これを何度も繰り替えす
1点探索 (move)
他の広告の邪魔になっているところを解消するため、広告を平行移動する 広告を一つランダムに選択する 任意の方向に適当な距離移動させることを試す
2点探索 (redelineate)
接触している2つの広告のペアをランダムに選択する 接触している境界線をどちらかの方向に適当な距離移動させることを試す
スコア計算の最適化
- 解の条件を満たしているかを判定するのがO(n2)かかっており、遅い
- 操作前に解の条件を満たしていることを仮定すると、上記の操作では、変更した広告と他の広告のペアについて、解の条件を満たしているかを判定すれば十分
- 判定にO(n)、スコア計算にO(n)で全体でもO(n)でスコアを計算できる
- また、スコア計算自体も差分更新できる（依然として判定にはO(n)かかるので、オーダーレベルでの改善にはならない）
- そもそも、スコアをずっと持っておく必要もなく、スコアが増大するかどうかが関心の対象なので、変更した広告の得点だけを見ればよい
greedy
何度も改善を繰り返し、制限時間を迎えたとき、shake操作等により広告間に隙間ができていることがある もったいないので、改善できるなら貪欲に改善する
redelineate skip 最適化
自明解から広告を拡大している途中では、広告同士が接触していることはまれ 2点探索は接触判定にO(n2)かかっており遅いため、最初のうちは行わないことで高速化
全体再配置 (gravity)
方向をランダムに選択する すべての広告を、他の広告にぶつからず、位置の制約を満たす範囲で選択した方向に平行移動する この際、平行移動の代わりに拡大してスコアを改善できれば、する
1点探索 (resize_2way)
1方向だけに対してサイズ変更をした場合、すでに要求の大きさに近い面積になっていると、これ以上拡大・縮小が不可能になることがある 2方向に対してサイズ変更をすることで、これを緩和する
複数回探索 (多点スタート)
局所解に嵌ってしまうと、抜け出すのは困難なため、何度も探索してもっともよさそうな解に対してさらに最適化を掛ける
2点探索高速化
2点探索では、接触判定の計算量O(n2)が支配的で、その後の試す部分では解の条件判定にO(n)掛かる他は定数時間で終わる。 そのため、一度接触判定をしたら、その後たくさんのペアに対して変更を試すことで、変更当たりの計算量を削減して高速化できる。
2点探索 (dodge)
接触面を平行移動するのではなく、接触面を0にするようにそれぞれの広告の大きさを変更した後、もとよりスコアが改善するように接触面のあった方向に広告を伸長する
resize_1way強化
resizeの結果他の広告にぶつかった場合も、そこで失敗判定にせずに、ぶつかった広告を縮小して回避できるときは回避することを試す
