マラソンマッチ風でした。round2寝落ち勢です。
たぶん17位で通過です。
実際にコンテストでマラソン参加するのは初めてでした
問題は、大体だと、w*hの枠が与えられて、長方形がN個与えられて、長方形はそのままor90度回転させて、0.1倍から2.0倍に大きさを変えて、マップ内に完全にはいって、
他の長方形と重ならないなら置ける（おかなくてもよい）
N<=100で、細長いマップの時はそれと似たような長方形が多い!!重要!!
回転させていない長方形と、回転させた長方形が接する長さを最大化せよ。回転させていないものどうし、回転させたもの同士が接するとその長さだけマイナス。
戦略
- 1.横にして使うものと、縦にして使うもので分ける。横・縦の比が基準で、横に細長いのを作る。マップによって偏りがあるので、だんだん多いほうから少ないほうに移してゆく。
- 2.マップが縦長になるよう必要ならば回転させて、何列かに分けて、列の大きさを決める。横に細長くて、列にうまくフィットするものから詰めまくる。細長いのは面積辺りの接する長さが多いので。
- 3.あとは、同じ列では、幅が長いのから順に置いたほうがよいので、1列置き終わったらソートする。
- 4.最後に、微妙に余ったスペースに余り物を詰めまくる。
細かい改善としては
- 縦に細長い（ダメな）長方形は、縦の長さが同じだったらマージ。これをすると余り物が使い物になる（ただ同じなものはなかなかない、lcmをとるなども考えたがサイズ変更が制限される上実装が面倒）
- 4番目の、最後に詰めまくるのが意外とスコアが大きいので、列の幅に完全にフィットするものは本来スコアが高かったが、列の幅*0.85ぐらいにフィットするものは完全にフィットするのと同等の評価にした
- あとは各種パラメータを調整して、Run
- 4番目の改善は実際に置いてみないと分からないので、パラメータごとに答えを出してもっともよいものを選ぶ、といった感じ
感想としては
- 思いついたもののほとんど効果がない・実は勘違い、ということがかなりあって、実装する前にもっともっと考察すべきだなぁ、と感じた。
- 時間が長いからといって（長いからこそ）すぐ実装するのではなく、それで本当によいのか考えるべきだと思った
- まあ、初参加にしては、通過できたのでよかったぁ～と安心
- 1日目1位になったりして、途中だいぶだらけていて、終盤1日で10位下がったのにはビックリした。巻き返し激しすぎw
- 実は最後のほうのpretestでは26位で、だいぶ落ちたなーと思っていた。細長いケースがpretestでは少なく、それでやや助かった面もある(長方形のマージは細長いとき役に立つ)
- コードがかなり長くなるので、こういうときは高機能なIDEもいいかもしれないな～と思いつつも、最近VisualStudio触ってないので使い方が分からない
↓適当なマップの画像
("phidnight"をジェネレータに投げると出るマップ)
("383129"をジェネレータに投げると出るマップ)
