Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2010-05-10Marathon Match 58/59

Marathon Match 59

| Marathon Match 59 - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク - Marathon Match 59 - hama_DU@TopCoderへの道

http://www.topcoder.com/longcontest/?module=ViewProblemStatement&rd=14227&pm=10885

指定された大きさの本棚に、本をなるだけ効率良く詰める問題。

本ごとに大きさと点数が決まっているため、

なるだけ効率のよい本(小さくて点数の高い本)を

ふんだんに使うことがポイントとなる。


とりあえず

点数の高い順に本棚に詰めていくプログラムを書いてみた。

提出。35.2万点。


高さ的に残念なことになっている本同士を入れ替える

異なる棚にあって、本同士を入れ替えても幅をオーバーせず、

棚の高さを節約できる場合は入れ替え、高さを稼ぎ、

余った本を使って残りを埋めるプログラムを書いた。

提出。36.8万点。


点数の高さよりも、効率のよい本を使ったほうがいいかな?

本を点数効率(=本の点数÷本の面積)の高い順に入れ替えて、

上記と同じ手法を試してみた。するとローカルテストで40万点代突破!

きたこれ。

この後、ある棚の本に対して、複数の本で入れ替えたほうが点数がいいなら

それらで置き換えたり、点数効率の上位のみしか使わないようにしてみたり、

その他パラメータをいじくるも、あまり点数は伸びず。

提出したものは40.3万点を獲得。


本を高さでグループ分けしてみる

高さが76~80の本、81~85の本、86~90の本・・・という風に

本をある一定の範囲の高さでグループ分けして、

同じグループの本を隣通しで使ったら効率がいいのではないかと考えた。

どういう順番でグループを本棚に入れるかを深さ優先探索し、

残り時間が0.15を切ったら、パターンのうち最高得点を出した組み合わせを暫定解とし、

後は本を入れ替えたり高さを稼いだりごにょごにょする・・・

というプログラムを書いた。

これならば、高さがあまり無駄になることがないのではないか、と。

範囲を15に設定して提出。42.9万。きました!


暫定解を求めるときに

最高得点の更新の様子をローカルテストで確認したところ、

ある程度点数が更新されると、時間切れ(1.85s)まで更新されないことに気づいた。

そこで、一定時間最高得点の更新がない場合は、

暫定解の探索を打ち切るようにしてみた。

ローカルで試してみると、あまり点数は落ちなかった。

そこで、グループ分けのパターンを変えたものを3通り用意し、

それらについて暫定解の探索を行うようにしてみた。

  • 高さが76~80の本、81~85の本、86~90の本
  • 高さが77~81の本、82~86の本、87~91の本
  • 高さが78~82の本、83~87の本、88~92の本

のようにグループとする高さを少しずつずらしたものに対して

探索を行い、最もよい暫定解を元に

本を入れ替えたり高さを稼いだりごにょごにょする・・・

というプログラムを書いた。

現状このアイデアでは、グループ化範囲を5に設定したものが

最も高得点がとれたので、提出。45.5万。

暫定解探索時の枝狩り

暫定解を探すとき、棚の途中でグループの本を使いきってしまった場合は、

仕方なく他のグループの本を使うことになるのですが、

この使うグループの高さが余りにもかけ離れている場合は、

「どーせ大した点数こないだろ」ということで探索を打ち切るようにしてみた。

これでパラメータを調整しつつ提出。45.9万。頑張った俺。


結果

94位/312人。しょっぱいなぁ。

rating微減するも何とか黄色キープ。(1578→1559)