Hatena::Grouptopcoder

(iwi) { 反省します

TopCoder: [[iwi]] / Twitter: @iwiwi

 | 

2012-04-04

VK Cup 2012 Wild-card Round 2

02:24 | VK Cup 2012 Wild-card Round 2   - (iwi) { 反省します を含むブックマーク はてなブックマーク - VK Cup 2012 Wild-card Round 2   - (iwi) { 反省します VK Cup 2012 Wild-card Round 2   - (iwi) { 反省します のブックマークコメント

マラソンだった.Pretest で 2 位になってから潜伏して,もう通るだろと思って放置していた.結局かなり抜かれたなあ.

戦略

Greedy → Local Search

定番すなあ.

Greedy

長方形を,順に置いていく.置くとき,スコアが最大になる場所におく.サイズは適当に制限しないと最初のほうでかくなりすぎるので適当に制限.

頑張ってそこそこ高速化したが,100 個あって,毎回どれを置くかまで全てから選択するのは無理だったので,N 大きい時は,ランダムに 20 個ぐらい試して一番いいの置く.

Local Search

適当に取り出して,別の順でまたグリーディに置く.

感想

こうやってみると本当に普通のことしかしてないな.

置く・取り出す・措くべき場所列挙,を高速にやるのが結構しんどいかんじで,結局ちょっとがんばったがもっとがんばれそうな感じだった.でも TLE 10 倍にして 50 秒とか手元で実行してもそーこまでスコア伸びなかったからそういう問題じゃないかも.

時間あると Greedy いっぱいやるわけだけど,Greedy で出てくるスコアは結構大きなばらつきがあるので,そこは改善の余地がありそうな気がしたけどわからんかった.

Greedy を,最初はランダムに 1 個選んで最適な場所に置く,だったのをランダムに 20 個とか小さい N には全部を試すようにしたら凄い伸びたので,1 個先まで読むの書いたらやっぱり凄い伸びるだろと思ったけど全然伸びないどころか遅くなった分悪くなった.悲しい.終盤だけ読むようにしても全然.なんでかな〜?

 |