アジの開きを閉じる。

競プロ(AtCoder)中心のブログ

【解説】ABC263 D - Left Right Operation

ABC 解説

執筆時レート：緑

問題文→https://atcoder.jp/contests/abc263/tasks/abc263_d

公式解説→https://atcoder.jp/contests/abc263/editorial

目次

問題
制約
解説
実装

問題

長さ $N$ の整数列 $A = (A_1, A_2, ..., A_N)$ 対し、以下の連続する操作を一度だけ行う。

　Step $1$ : 先頭から $0$ 個以上を選び、それぞれ $L$ で置き換える。

　Step $2$ : 末尾から $0$ 個以上を選び、それぞれ $R$ で置き換える。

操作後の $A$ の要素の総和として考えられる最小値を求めよ。

制約

$1 \leq N \leq 2 \times 10 ^{5}$
$-10^{9} \leq L,R \leq 10 ^{9}$
$-10^{9} \leq A_i \leq 10 ^{9}$
入力は全て整数

解説

まず、 $L$ と $R$ で置き換える項がオーバーラップする操作が考えられますが、そのような操作は考慮しなくて良いです。

なぜなら、オーバーラップした操作後の数列は、 $R$ で置き換えられない項だけはじめに $L$ で置き換える操作と同じ結果になるからです。

よって、Step $1,2$ で置き換える範囲が重ならないように操作するものとして考えることができ、そうすることで数列を分割した次の考え方ができます。

数列を位置 $k \, (0 \leq k \leq N)$ で $2$ 分割します。左側の部分でStep $1$ 、右側の部分でStep $2$ を行い、各部分の操作後の総和の最小値がこの分割での総和の最小値となります。この最小値を $f(k)$ とします。

すると、求める答えは $k$ を $0 \leq k \leq N$ で全探索したときの最小値 $\min f(k)$ になります。

数列を $2$ 分割することは、つまり、その境界によって $L$ や $R$ で置き換えられる最大項数を制限していることになります。

すべての制限を調べることによって答えが求まるということです。

次に、 $f(k)$ の求め方を考えます。 $2$ つの関数 $lmin(k), rmin(k)$ を、

　 $lmin(k) :=$ 位置 $k$ より左側でStep $1$ を行った後の総和の最小値

　 $rmin(k) :=$ 位置 $k$ より右側でStep $2$ を行った後の総和の最小値

とすると、 $f(k)$ は

　 $f(k) = lmin(k) + rmin(k)$

となります。

$lmin(k), rmin(k)$ の値はDPによって求めることができます。

$lmin(k)$ を考えるとき、末項 $A_{k-1}$ を $L$ で $(i)$ 置き換える、 $(ii)$ 置き換えないの $2$ 通りに場合分けができます。

　 $(i)$ 置き換える場合、操作後の総和は $L \times k$ です。

　 $(ii)$ 置き換えない場合、操作後の総和の最小値は一つ前の位置 $k-1$ より左側でStep $1$ を行った後の総和の最小値に $A_{k-1}$ を加えたものであるので、 $lmin(k-1) + A_{k-1}$ です。

よって、 $lmin(k) = \min (L \times k, lmin(k-1) + A_{k-1})$ となります。

$rmin(k)$ も同様に求められます。

これでこの問題が解けました！

計算量は $O(N)$ です。

実装

C++による実装例です。

https://atcoder.jp/contests/abc263/submissions/33850906

添え字で混乱する場合は以下のイメージを持つと良いです。