けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder EDPC W - Intervals

AtCoder EDPCとTDPC DP in-place DP DP高速化:セグメント木 セグメント木 StarrySkyTree 区間 0と1の問題 操作 操作:区間 負値が本質的に効く問題

まさに、「DP 配列をセグメント木に載せる」というセグ木上の in-place DP ですね！！！

一部の競プロ界隈では、俗に実家 DP などと呼ばれてたりしていたものです。

問題概要

0 と 1 のみからなる長さ N の文字列を 0-1 文字列と呼ぶことにします。

今、文字列中の M 個の連続する区間 ( i 番目の区間を \lbrack l_{i}, r_{i} \rbrack とします) が与えられます。これらの区間を用いて、0-1 文字列 S のスコアは次のように計算されます。

  • 各 i = 1, 2, \dots, M について
  • 文字列 S の区間 \lbrack l_{i}, r_{i} \rbrack の内部に 1 が一個でも存在するならば、スコアに a_{i} を加算する

0-1 文字列のスコアとして考えられる最大値を求めてください。

制約

  • 1 \le N, M \le 2 \times 10^{5}
  • -10^{9} \le a_{i} \le 10^{9}

解法

もし a_{i} がすべて非負であったならば、 S = 111...1 が最適でしょう (その場合のスコアは \sum_{i = 1}^{M} a_{i} となります)。

実際には a_{i} が負値となることもありますので、その場合は区間内部はすべて 0 にしておきたいところです。しかしそうしますと、他の正値なスコアを取りこぼしてしまう可能性もあります。このように「全体のバランス」を考えないといけない場合は、DP で解決できる場合が多々あります。

さてこの問題は、結果的に DP 配列自体をセグメント木 (特に Starry Sky Tree) に載せて in-place に更新するような解法で解けます。in-place DP について特集した次の記事で詳しく解説しました。

qiita.com