昨日見た時点では160位とかだった。
方針概要
領域を縦線 or 横線で2つに分断していくこと繰り返すような操作を考える。途中まではKDTreeみたいな気持ちで、Depthが奇数のときは縦、偶数のときは横みたいにすることを意識していた。それを全日で固定とする線をできるだけ多く作るようにしたい。
最終的には結局縦横どっちに分割するかも最適化要素に入れた。そうすると、各深さで決めるべきは
- どちらの方向に分割するか
- どれだけの長さで分割するか
- 分割した2つの領域にどの予約を割り当てるか
になる。方向は0 or 1、長さは切る方向の全体からみた割合として、分割はできるだけ面積の差が少なくなるように後ろから振り分けていくとして焼き鈍し状態を定義して、適当に焼く。あまり時間をかけても改善しなかったので良い方法ではなかったのだと思う。
シート0001とかは全然固定線を作れていない。
かけた時間
| 日 | 時間 | やったこと概要 |
|---|---|---|
| 1日目（金） | 1時間くらい | ちょっと問題読んで環境整備 |
| 2日目（土） | 4時間くらい | 各予約の長方形を独立に焼き鈍す。全然スコアが出なかった |
| 3日目（日） | 0 | - |
| 4日目（月） | 2時間くらい | ここでKDTreeみたいに分割していくアイデアを思いつく。ようやく面積を溢れさせないような振り分けができるようになり、多少スコアがまともになる。250位くらい？ |
| 5日目（火） | 1時間くらい | 評価関数で区切り線の生成分解によるコストをようやく考慮する |
| 6日目（水） | 2時間くらい | KDTree的区切りをして、各ターンでの振り分けをランダム化してそこを山登り法で最適化してみたが上手くいかず |
| 7日目（木） | 4時間くらい | ようやく全日通して固定する線を決め打ちする実装を入れる。多少スコアが良くなる。200位くらい？ |
| 8日目（金） | 0 | - |
| 9日目（土） | 6時間くらい | 高速化したり時間いっぱい回すようにしたり分割をスワップするようにしたり。150位くらい |
| 10日目（日） | 1時間くらい | 遷移の調整程度 |
| 11日目（月） | 0 | - |
計20時間程度か。苦手めな問題で、あまりやる気も高まらなかった。もう一つくらい発見をして多少順位伸ばせれば良かったが、日曜日にAGCがあったのもあり、力尽きた。
