かしのブログ

競技プログラミングとか

Kyoto University Programming Contest 2019 F - カズマ王国の陥落

AtCoder DP セグメント木

問題

王国に $N$ 個の街がある。魔王が $i$ 番目の街にモンスターを $X$ 匹送ると、王国に $\max(0, X-A_i)$ のダメージを与える。魔王は $M$ 個の拠点があり、合計 $B_i$ のモンスターを $L_i, L_i+1, \cdots, R_i$ 番目の街に好きな配分で送り込める。王国に与えられダメージの最大値を求める。

考察

次のようなdpを考える。

${\rm dp}[i] \triangleq$ $i$ 番目の街に派遣し、 $i+1$ 番目以降の街は未定のときのダメージの最大値

とすると、以下の式で更新できる。

${\rm dp}[0] = 0$
${\rm dp}[r] = \max_{l \lt r} ({\rm dp}[l] + \max\{0, c(l+1, r)-A_r\})$

ただし、 $c(l, r) \triangleq \sum_{i \in [1, M]} \{B_i\ |\ l \leq L_i \leq r \leq R_i\}$

解は $\max_{1 \in [1, N]} {\rm dp}[i]$ 。

このままでは計算量は $\mathcal{O}(N^2M)$ でTLEになる。 $c$ の計算は範囲によって決まるので、セグメント木を使って高速に計算することができそうである。

${\rm dp}$ の $r$ が小さい方から計算して、セグメント木上では、常に $r \leq R_i$ を満たす拠点のみ計算するようにすると、拠点ごとにセグメント木の操作が追加と削除で2回になる。

これで計算量が $\mathcal{O}((N^2 + M) \log M)$ になった。

実装