VK Cup 2012 Wild-card Round 2

VK Cup 2012 Wild-card Round 2 (03/29~04/04)

VK Cup 2012 Round 2で大敗したのでチャレンジ．

問題

w*hの長方形領域に，n個の長方形を配置する．各長方形(wi, hi)には，回転，拡大・縮小を行うことが出来る．回転は90°単位で（つまり(wi, hi)が反転），拡大・縮小は0.1, 0.2, …, 0.9, 1.0, 1.1, …, 1.9, 2.0倍で可能．長方形は，互いに重なってはいけないが，接することが出来る．
（反転していない長方形と反転している長方形の接している辺の長さ）-（反転している/いない長方形と反転している/いない長方形の接している辺の長さ）
を最大化せよ．

制約

5<=n<=100
10<=w, h<=100
wi!=hi, w/10<=wi, h/10<=hi, 0.1<=wi/hi<=10 (0<=i

解法

縦横比が極端なものを交互に配置していき，その後，余った領域に長方形を埋めていく．以下，詳細．

A: 5<=n<=15の場合

n個の長方形をシャッフル．
各長方形についてstep2を実行．
1.に戻る．

nが大きい時のような規則性が出ないと判断したため，様々な順番で長方形を配置することにした．

B: 16<=n<=25の場合

縦横比（=wi/hi）を基準にして長方形をソートし，長方形を両端から拾っていく．下図のような順番になる．
2回だけ，無作為に選んだ2つの長方形を交換する．
step1を実行．
step1で余った長方形についてstep2を実行．
1.に戻る．

2. の交換は，何故か上手くいくので採用した．

C: 26<=n<=100の場合

縦横比を基準にして長方形をソート．この時，乱数を用いて縦横比を少しだけ変化させる．その後，長方形を両端から拾っていく．
step1を実行．
step1で余った長方形についてstep2を実行．
1.に戻る．

1. で縦横比を少し変化させたのは，幾つかのケースを試すため．

step1

貪欲に長方形を並べていくフェーズ．縦横比が交互になるようにソートされているので，並べるだけ並べていくと最終的に以下のようになる．

赤い長方形は，90°回転させたもの．もし，長方形領域が縦長だったら，全体を回転させたものになる．
また，全体の長方形領域に対するマージン（marginXとmarginY）を予め設定しておいて，step2を行うための領域を確保しておく．

step2

余った領域に長方形を埋めるフェーズ．全ての座標を探索するのは計算量的に無理なので，既に配置してある長方形の4隅の座標とその座標の4近傍を候補とした．各候補の座標に長方形を配置し，最もスコアが高くなる座標を採用．
極端に大きな長方形を配置する時，以下のような配置が発生する事がある．このケースは，スコアの増加量は大きいものの，その後も長方形を配置することを考えるとスマートとは言えない．そのため，スケーリング後の長方形の面積がmaxAreaを超えたら不採用とする，という制限を追加した．

チューニングパラメータ

nの値による解法の切り替え（人力で調整）
マージンの設定（marginXとmarginYを人力で調整）
Cの縦横比の変化量（人力で調整）
step2でのスケーリング（人力で調整．n>=16の時は，1.0倍を超えるスケーリングを行わなかった）
step2でのmaxArea（人力で調整．n<=15の時とn>=16の時で異なる算出方法をとった）

ボツ解法

既に出来上がっている長方形配置に対して，新しい長方形を左手法のように動かしながら配置座標候補を探索．一番最初に組んだ解法かつ左手法の実装が難しかったが，スコアが低かったのでボツにした（ただしこれのお陰でstep2に繋がった）．

反省点

チューニングパラメータが多すぎた．しかも人力調整だらけだったので，非常に面倒だった．
ローカルテストが相変わらず適当．もう少しケース数を増やすべき．
nについての解法切り替えは出来たが，w/hによる解法切り替えも考えるべきだったかも知れない．
nが小さい時の解法が甘い（iwiさんのように局所探索系を採用するのが有効）．もし，Marathon Match 74のように，一様分布な変数aに対してn=10^aだったら，多くの人に抜かされた可能性がある（とはいえ，nが小さい時は，出現頻度が低いため全体のスコアに大きく影響しない事も計算済みだった）．
ビジュアライザを効果的に活用出来た．具体的には，長方形を配置していく過程とビジュアライザを同期させたため，長方形を配置する座標の候補として1ピクセルだけずらした4近傍を思いつくことが出来た．また，初期の段階では，スコアの高い解・低い解を見ることで，step1の処理を思いついた．
最終日に多くの人に抜かされ焦っていたが，抜かした人はpretestに固執した解法である可能性が高かったので，コードを調整したい衝動を抑えた．代わりにpretestには存在しない16<=n<=25のケースを特殊化した．
03/31になるまで気力が起きなかった．

考えていた（けど叶わなかった）改善点

判定関連の高速化

ある長方形を配置した時に既に配置されている長方形に重ならないか，及び重なっていない時のスコア増加量の計算量がO(n)から減らせなかった．そのため，候補座標の数が16n個なので，1つの長方形を配置するだけでO(16cn^2)（cはスケーリング等のパラメータ数）の計算量がかかってしまっていた．何か幾何系のデータ構造を採用することも考えたが，熟考する時間が取れなかった．