2010-09-29 - TopCoderの学習のお時間

なかなか赤い人に勝てない…

W*Hの盤面が与えられる。うちP%は使えないマス。

1回のクエリでK-ominoのピースとその価値が与えられるので、盤面の中にはめ込んでいく。パスしてもよい。

クエリが全部で何回来るかだけは事前にわかるが、それ以外の情報（次にどんな形のピースが来るか、その価値はいくつか）はわからない。

盤面の中にはめ込んだピースの価値の合計を最大化する。

10<=W,H<=100, 3<=K<=10, 0<=P<=30, 1<=各ピースの価値<=100

ピースの種類は等確率で出現するわけではなく、確率に重みが付いていて、ある形のピースがよく出たり逆に全然出なかったりする

ピースごとの価値に大幅な差があるので、安いピースを使ってしまわないのが重要。

「あとN回クエリが来て、盤面にあとM個ピースを置ける」というときに、価値がいくつ以上だったら使ったほうが良いかはDPで厳密に求められるので、それを閾値にする。

Mの値は (残り空きマス数)/1.05/K とかで適当に計算する。割り算の係数はKやPが大きいほど大きくなるよう調整

とりあえずこれをやってたら90点近くまではいくのではないかと

どれだけピースが隙間を作らずきれいにはまったかの評価関数を作って、それが最良となるところを探索してピースを置く位置を決定する。

評価に使ったポイントは以下

単純に実装すると大きな盤面では時間が足りずあまり探索できないので高速化も必要

このスコアリング方法では僅差の勝負になる上に、焼きなましのときのように自分で時間を計りづらいタイプの問題なので、TLEしないように気をつける

手元での最悪ケースが7秒で、サーバーではだいたいローカルの2倍くらい時間がかかるので、5秒くらいは余裕を持っているはず

終了近くでは、まだピースを置けるところを逃してしまわないように、使うかどうかの閾値を下げて安めのピースでも使う
ピースの価値が閾値よりちょっと低くても置く場所を探索してみて、評価関数の結果が過去のケースの平均よりもずいぶん良いようなら採用する
だいたい周囲から順に埋めていきたいので、探索は周囲から中央に向かって進めていく。周囲に近いところでは少し評価関数にボーナスを付ける
- 先に真ん中に置いてしまうと、のちのち盤面が分断されやすくなって使えるマス数が減る傾向になる
- これは枝刈りが効きやすくなるという点でも有効
盤面の周囲には番兵を置くとコーディングが楽
ビジュアライザをカスタマイズして自由に再生や巻き戻しができるようにした。ビジュアライジング重要

ピースの形ごとの出現回数の統計を取る
- 珍しい形のものが出てきたときは採用の閾値を下げたり
- ピースを置く位置の探索で、K個の孤立した領域ができたときにその形が良く現れるピースの形かどうかで評価関数への影響を変えたり
評価関数の項目に、空きマスの連結成分を大きく分断しないことを含める
- できるだけ連結したままの方が以降ピースを置きやすくなるので良いだろうと
新しくできる壁を評価するとき、2つの壁から囲われているマスについて、壁の形が"└"型か"||"型かで評価を変える
- 後者の方が、盤面の分断に繋がる可能性が高そうなので悪い評価にする
パラメタを山登り法で決定
- 100ケースでテストしてたもののオーバーフィッティングになりまくって意味がなかった
- きっと終盤ではとても細かい値での勝負になっていたせい（0.01%上がれば十分意味のある改善、というくらいの）