Educational Codeforces Round 15: F. T-Shirts
http://codeforces.com/problemset/problem/702/F
別の解があるようです。それと嘘解法の可能性があるので、あまり鵜呑みにしないでください。
問題
価格 価値 の商品が 個ある。客 は 円持っている。客は買うことのできる最大価値の商品を買う(複数あれば安い方を買う)という戦略を取る。同じ商品は二度買わない。
それぞれの客が買うアイテムの個数を求めよ。
解法
で降順ソートすれば、使う順番は必ず 0→n-1 になる。このことを用いると次のような DP ができる。
$$ dp[ i ][ money ] = \begin{cases} dp[i + 1][ money - w[i] ] + 1 & (w[i] \le money ) \\ dp[i + 1][ money] & (w[i] > money) \end{cases} $$
しかし状態数 2*105*109 なのでループで更新するのは難しい。
そこで"永続"平衡二分探索木を用いる。merge/split が使って次のような更新をすればいい。
- dp' = dp[0..w[i]-1] ++ (dp[0..N-w[i]-1] + 1)
merge/split の計算量は O(log n) だし、一様加算も遅延伝搬できるので問題ない。ところで 109 個頂点作った時点で MLE するのではと思うかもしれないが、永続を使えば陽に 109 個のノードを作る必要はない。次のような処理で 230 の木を作れる。
dp = node() for i in range(30): dp = merge(dp, dp)
計算量は時間・空間ともに O((n+k) log 10^9) だが、実際にはメモリが足りなくなる。永続はどこからも参照されていないノードが生じがちなので、こういうのを回収するとメモリ不足は解決できる。
怪しいのは不要なノードの個数で、これが評価できなかった。もし木のサイズが 105 程度であれば、105 個のノード以外は無駄なノードだとわかる。しかし今回は木のサイズが 109 なので、その考え方では抑えられない。
自分が試した限りだと結構残るケースというのも存在した。
テストケース | 回収後の使用ノード数 |
---|---|
[1..103] のランダム | 2,569,935 |
[1..104] のランダム | 4,675,029 |
[103..104] のランダム | 5,547,043 |
[1..2*105] のランダム | 390,006 |
[1..109] のランダム | 2,120 |
109,109-1,109-2,... | 200,923 |
1,2,3,...,2*105 | 724,060 |
残るとは言っても 30,000,000 ノードまでは余裕で確保できるので問題になる数値ではない。しかし適当に作ったケースでこのノード数なので、もっと練りこめば落とせるような気もする。
あと、RBST を使うと高さが爆発するケースが増えたようだ。ちょっと工夫すれば大丈夫なのかもしれないが、赤黒木を使った方が安全だろう。RBST の高さがおかしくなるのは実装のせいなのか、原理的に無理なのかどっちなんだろう。