pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Codeforces Round #342 (Div. 2) D. Babaei and Birthday Cake

codeforces.com

解法

次のような DP ができる。

  • dp[最後に使った体積] := 体積の総和の最大値

体積 r[i]*r[i]*h[i] は最大で 1012 になってしまうので一見この DP は不可能に思えるが、体積を座標圧縮すれば可能になる。

更新するときは最後に使った体積が v' 未満のものに v' を付加させることを考えればよい(v' は圧縮後の v の値を表す)。

  • dp[v'] = max(dp[v'], max(dp[0], dp[1], ... , dp[v'-1]) + v)

min(dp[0], dp[1], ... , dp[v'-1]) を愚直にやると間に合わないので RMQ を使おう。


Codeforces Round #343 (Div. 2) D. Babaei and Birth ...


BIT でも実装可能。
Submission #16256777 - Codeforces


座標圧縮する代わりに動的セグ木を使うという手もある。ある意味素直な方法。
Submission #16257714 - Codeforces

動的セグメント木というのは必要になるまでノードを構築しないセグメント木のこと。 ノードを動的に構築することで広い区間を扱えるようになる。最大の区間幅を n としたとき一回の更新クエリで高々 lg n 個のノードが作成されるため、メモリ使用量は O(Q lg n) となる。
strictly を考慮し忘れても pretest は通るらしい。