AtCoder Beginner Contest 249 F問題 Ignore Operations

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

$0$ で初期化された変数 $x$ がある. $i=1,2, \dots, N$ の順に以下の操作を行う.

$t_i=1$ ならば, $x \gets y_i$
$t_i=2$ ならば, $x \gets x+y_i$

ただし, この $N$ 個の操作のうち, 高々 $K$ 個の操作を無視することができる.

このとき, 最終的な $x$ の最大値を求めよ.

制約

$1 \leq N \leq 2 \times 10^5$
$0 \leq K \leq N$
$t_i \in \{1,2\}$
$|y_i| \leq 10^9$

解法

$t_i=1$ のときの操作は代入であるが, 代入操作をする場合, $(i-1)$ 番目までの操作は最終的な結果には一切影響を与えない. そこで, 最後にいつ代入を行ったか (または, 一切代入をしない) で場合分けし, 最大値を求めることにする.

$t_i=1$ となる $i$ を $1 \leq p_1 \lt \dots p_k \leq N$ , $t_i=2$ となる $i$ を $1 \leq q_1 \lt \dots \lt q_{N-k} \leq N$ とする.

代入を一切しない場合を考える. これは $k \lt K$ の場合はできない. よって, $k \leq K$ とする. このとき, $y_{q_j}~(j=1,2, \dots, N-k)$ の中から高々 $K-k$ 個を取り除いて和を最大にする問題になる. これは

$y_{q_1}, \dots, y_{q_{N-k}}$ にある負の個数が $(K-k)$ 個以下ならば, 非負の総和が解の候補になる.
$y_{q_1}, \dots, y_{q_{N-k}}$ にある負の個数が $(K-k)$ 個より多ければ, 小さい方から $K-k$ 個を除いた総和が解の候補になる.

最後に行う代入が $p_j$ 番目の操作であるとする. そして, $q_{l-1} p_j \lt q_l$ であるとする. このとき, * $y_{q_l}, \dots, y_{q_{N-k}}$ にある負の個数が $(K-k+j)$ 個以下ならば, 非負の総和が解の候補. * $y_{q_l}, \dots, y_{q_{N-k}}$ にある負の個数が $(K-k+j)$ 個より多ければ, 小さい方から $(K-k+j)$ 個を除いた総和が解の候補.