■ [TCO][MM] TCO14 Marathon Round2 
http://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=15982&pm=13189
問題
ランダムな大きさの長方形がN個与えられる。長方形の各辺の長さは[1,1000]、Nの範囲は[100,1000]の一様分布。
こいつらを平面内に配置して穴を作る。
(穴の個数)^2 * (穴の面積合計) を最大化せよ。
やったこと
大きな穴を1つ作る+小さな穴をたくさん作る が最適になるのはまあ直感的にわかる。
colunさんに倣ってBigHoleとManyHolesと呼ぶ。
ManyHolesに何個の長方形を回すかは、実験してみたらN*0.54くらいが良さそうだった。
ManyHolesを作るときは、BigHoleで使われている長方形も利用した方がManyHolesに寄与する長方形の数を稼げる（その結果穴の数が増える）ので、BigHoleにくっつけて作る。
ManyHolesの領域はできるだけ表面積を小さくした方が良い（N個の長方形から作れる穴の数の最大値はNが大きいとほぼN個なんだけど、領域の外側に出ている長方形の個数分その限界から遠ざかっていく）ので、ManyHolesの部分は丸い感じになるようにする。
そのため、BigHoleの作り方を工夫して一部を外側に張り出すようにした。それでできた空間に小さい長方形を詰めていく。
小さい穴をたくさん作る方法なんだけど、賢い配置を考えて決めるのは泥沼っぽい気がして探索することにした。
長方形を小さい順に取って、既存の長方形の右側か左側に接するところを試す。他の長方形に接する一番端の箇所を見つけて、隙間ができていたらそれを穴ができたと見なす。
| | |
| | |
| +---+
-+ | +---+
| +---- | |
|+----+ や -+| |
|| | |+---+
|| | |
|+----+ |
| |
-+ -+
こんな感じだと良い配置。
時間制限いっぱいまで、使う長方形の順序をちょっと変えながらこれを繰り返す。本当はビームサーチしたほうが良いのだと思うけど、実装時間が足りなくて断念してしまった。
あと、BigHoleの内側にManyHolesを作るのではなく外側に作ったら、面積が2%くらい増えるなーと思ってたけど、どうやっても穴の個数が減ってしまってうまくいかなかった。
画像
seed=1の例。
全体：
上部：
ビジュアライザには次の変更を加えた。
- 穴になった部分が赤く塗られていたけど気持ち悪かったので消した
- スクロールやズームを可能にした
- 縮尺を表示するようにした
- ビジュアライズ部分をテスタと分離して別プログラムにして、テスタ実行時に表示するのではなくスタンドアローンで起動できるようにした
- テスタではログに出力しておいて、ビジュアライザにはそれを読み込ませる
結果
- provisional score : 954551.54（各ケースで1位を100万点とした相対スコアの平均）
- provisional rank : 9 / 170
- final score : 954969.99
- final rank : 10 / 170
- レーティング : 2188->2250
意味のあるスコアを出すまでの実装が大変なのでやっぱり参加者少なかったですね。
