Marathon Match 59

TopCoder

TCOのシードを得るために一年ぶりに参戦
結果は11位orz
まぁ、久しぶり過ぎた上に時間がなさすぎたのでしょうがない…
方針はまず、何段にするかと、それぞれの段の高さを決めるために、次のように制約をきつくした問題を考え、それを解くことにした。

  • i段目に入っている本はi+1段目に入っているどの本よりも高さが低い

こういう制約を付けると次のような二段階のDPにより最適解を求めることができる。

  • まず、本を高さでソートする
  • dp1[i][j] := [i,j]から幅Wで選ぶときの最大価値
  • dp1[i][j]の計算はiを固定しておいて、ナップサックするだけ
  • サイズが大きいと計算量がやばいので、ナップサックDPは諦めて貪欲法を使用
  • dp2[h][i] := i番目までで高さがhとなるときの最大スコア
  • dp2[h][i]=max{dp2[h-book[j].height-10]+dp1[j][i]}みたいな感じ
  • こっちも計算量がやばいので、嘘DPを使用

何段にするかと、高さが決まったら、次は高さの低い段から貪欲的にナップサックDPを行って本を入れる
これだけだと、空きスペースができてもったいなかったので、本を別の段に移動させることにより、新たに別の本が入れれるようになるっていうのを探して頑張って詰め込む
時間が余るので、高さをランダムにちょっとだけ変更して繰り返しー