Educational Codeforces Round 15: F. T-Shirts

http://codeforces.com/problemset/problem/702/F

別の解があるようです。それと嘘解法の可能性があるので、あまり鵜呑みにしないでください。

問題

価格 c_i 価値 w_i の商品が n 個ある。客 ib_i円持っている。客は買うことのできる最大価値の商品を買う(複数あれば安い方を買う)という戦略を取る。同じ商品は二度買わない。

それぞれの客が買うアイテムの個数を求めよ。

  •  1 \le n \le 2\cdot 10^5
  •  1 \le c_i, q_i \le 10^9
  •  1 \le k \le 2\cdot 10^5
  •  1 \le b_j \le 10^9

解法

 (w_i, -c_i) で降順ソートすれば、使う順番は必ず 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 の高さがおかしくなるのは実装のせいなのか、原理的に無理なのかどっちなんだろう。