AtCoder Heuristic Contest 001(AHC001) -AtCoder Ad- 参加記
問題
結果
989,207,448,084点で33位。パフォーマンスは2385。橙は相当厳しい…。もう少し上に行けるようになりたい。
方針
- 一つの長方形の1辺を拡大
- 一つの長方形の1辺を拡大・1辺を縮小
- 二つの長方形が縦(横)に接していたら横(縦)に接するように変形
の3つの近傍を作り、「1・2で山登り、3で焼き鈍し」を交互に行った。
近傍1
一つの長方形の1辺を拡大する。拡大する方向に別の長方形がある場合は、その長方形は縮小させる。高速化として、各長方形をxmin, xmax, ymin, ymaxそれぞれをキーにしてhash mapに登録しておき、長方形同士の接触判定をするようにした。
近傍2
一つの長方形の1辺を拡大・1辺を縮小する。近傍1だけだと、面積は長辺と短辺の長さ分の増加に限定されるので、長辺-短辺の増加も行えるようにした。
近傍3
二つの長方形が縦(横)に接していたら横(縦)に接するように変形する。近傍1・2だけだと局所解にハマるので、この近傍で焼き鈍しを行った。変更後の1辺の長さは最初は適当なルールで固定にしていたが、乱数で決めるようにしたらスコアが伸びた。1辺の長さを決めたらもう1辺の長さは、他の長方形に干渉しない範囲で目標面積にできるだけ近づける。
その他
- 近傍で選ぶ長方形の候補を、最初は閾値よりスコアが悪い長方形としていたが、近傍1・2ではほぼ全てを候補、近傍3では悪い方から一定の個数とするとスコアが伸びた。
- 他の人の解法によく出てくる、kick(長方形を破壊して再構築する)も途中まで採用していたが、kickを無くして近傍3の試行回数を稼ぐ方がスコア伸びたので不採用とした。
- 面積が大きい長方形の配置が大変なので、大きい長方形を先に配置してしまえば良いかと思ったがスコアは悪くなった。
反省点
- ビジュアライザは配布されたもので最終状態しか見てなかったので、途中の状態をちゃんと可視化して考察するべきだった。そのあたりが素早くできるようになりたい。
- 最終的な方針が固まったのが終了数時間前だったので、パラメータ調整が全くできなかった。最終日はパラメータ調整に費やせるくらいのスケジュールで進めたい。
