Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 263 D問題 Left Right Operation

AtCoder ABC ABC263 D問題 400 pts

問題

提出解答

問題の概要

長さ $N$ の整数列 $A=(A_1, \dots, A_N)$ がある. 以下の操作を順に1回だけ行う.

$0$ 以上 $N$ 以下の整数を1個選ぶ. その後, $1 \leq i \leq x$ を満たす全ての整数 $i$ に対して, $A_i \gets L$ とする.
$0$ 以上 $N$ 以下の整数を1個選ぶ. その後, $N-y+1 \leq j \leq N$ を満たす全ての整数 $j$ に対して, $A_j \gets R$ とする.

操作後の $A$ の総和の内の最小値を求めよ.

制約

$1 \leq N \leq 2 \times 10^5$
$-10^9 \leq A_i \leq 10^9$
$-10^9 \leq L,R \leq 10^9$

解法

元となる数列は $A$ で固定であるから, 操作前後で $A$ の総和の差分をどれだけ小さくできるか? ということに帰着される. ここで, $0 \leq x+y \leq N$ であると仮定しても一般性を失わない.

$x=0,1, \dots, N$ に対して, $\Delta_x$ で第1段階で $x$ を選んだ場合の差分の最小値とする. このとき,

$\displaystyle \Delta_x=\sum_{i=1}^x (L-A_i)+\min_{0 \leq y \leq N-x} \left(\sum_{j=N-y+1}^N (R-A_j) \right)$

である. このとき, $x=0,1,2 \dots, N$ の順に求めることにすることで, 第1項は各 $O(1)$ 時間で求められる. 第2項についても $x$ が $1$ 増えると対象となる項が $1$ だけ減り, それ以外の項については不変である. よって, 順序付集合を利用して適宜更新していくことにより, 各 $x$ に対して計算量 $O(\log N)$ で求められる.

以上から, $\displaystyle \sum_{i=1}^N A_i+\min_{0 \leq x \leq N} \Delta_x$ が答えであり, 計算量も $O(N \log N)$ 時間で求まる. また, 第2項の部分を工夫することにより, $O(N)$ 時間でも求めることができる,