AtCoder Heuristic Contest 001に参加しました

最終順位は17/1382でした。
順位表

問題
問題ページ

AtCoder社はトップページにスポンサー企業 n 社のWeb広告を設置することにした。 広告を設置するスペースは 10000×10000 の正方形をしており、各企業毎の広告スペースは軸に平行な長方形で正の面積を持ち、頂点の座標は整数値でなければならない。 異なる長方形は辺を接してもよいが、重なってはならない。つまり、共通部分が正の面積を持ってはならない。 どの広告にも属さない空きスペースが残っても構わない。

やった事

　焼きなまし１　温度は低温でほぼ山登り？　希望面積は半分からスタートする　4800ms

• ランダムに広告を選ぶ　か　スコアが低い順4分の1中から広告をランダムに選ぶ
• 選んだ広告に接している広告も選ぶ（接していないならランダムに１つ選ぶ）
• 選択した広告の大きさを1にする
• 最初に選んだ広告から拡大する。他の広告と重なったらあきらめる。拡大する方向はランダムで希望面積の大きさで少し変えるけど2000を1回, 800を1回, 400を1回, 200を2回, 100を2回, 50を2回, 10を2回, 5を2回, 1を2回と拡大してこれを8回

　焼きなまし２　160ms

• ランダムに広告を選ぶ
• 選んだ広告をランダムに少し拡大する各辺を０～３９。他の広告とかぶったら可能なら他の広告を小さくする不可能なら拡大をあきらめる

提出一覧