TopCoder MM59
概要
はじめてのまらそんまっち
4921.0000 + 3924.0000 + 3909.0000 + 5622.0000 + 3230.0000 + 6120.0000 + 1640.0000 + 2810.0000 = 23083695.00
96位
Rating: NON-RATED → 1397(blue) (+1397)
上出来です
問題
棚に高さ10の底板を複数とりつける。底板の上には本を収納する(横に並べる)。
与えられるのは、棚の高さと幅、各本の高さと幅と価値が与えられる。
棚に収納する本の価値の合計を最大化せよ。
基本解法
ある本の部分集合について、収納可能かどうかを以下で軽く判定する。
高いものから順番に走査する。最初の本にあわせてギリギリの底板を取りつける。その段に貪欲に本を並べていく。
入らなくなったら入らなくなった本の高さにあわせてまた底板を取りつける。
全て入れたときに段の高さの合計が棚の高さに入りきれば成功。
(価値÷幅÷高さ)が大きいものから順に、以下を実行する。
その本を棚に入れる本の集合に追加する。収納可能かどうかを判定し、不可能なら棚に入れる本の集合から取り除く。
改良1
収納可能かどうかの判定で、各段に余った領域ができる。
ある本が処理中の段に追加できなかった場合に、即座に新しい段を作るのではなく、余った領域に入れることができるなら、その本がギリギリ入る幅のものに追加する。
改良2
基本解法における処理が終了したあと、最も高い本を外してみて、さらに他の本が追加できないか調べていく。
まとめ
普通の山登りでもよかったかもしれない。
この手の問題は、距離1の近傍に対する山登りを行ったあとに距離2の近傍に対する山登りを行えばそれなりの解が得られるらしいので、そのような戦略を取ってみる価値はあったと思う。
距離2の近傍に対する山登りを全て行うとO(N^3)となり(N=700とかのケースがあるので)死亡するので、山登りにおける近傍を乱択(もしくは何らかの条件で選択)すれば良いかもしれない。
とにかく、はじめてにしてはじょーできだと思いました。
