AtCoder Beginner Contest 263 D問題 Left Right Operation
問題
提出解答
問題の概要
長さ の整数列
がある. 以下の操作を順に1回だけ行う.
以上
以下の整数を1個選ぶ. その後,
を満たす全ての整数
に対して,
とする.
以上
以下の整数を1個選ぶ. その後,
を満たす全ての整数
に対して,
とする.
操作後の の総和の内の最小値を求めよ.
制約
解法
元となる数列は で固定であるから, 操作前後で
の総和の差分をどれだけ小さくできるか? ということに帰着される. ここで,
であると仮定しても一般性を失わない.
に対して,
で第1段階で
を選んだ場合の差分の最小値とする. このとき,
である. このとき, の順に求めることにすることで, 第1項は各
時間で求められる. 第2項についても
が
増えると対象となる項が
だけ減り, それ以外の項については不変である. よって, 順序付集合を利用して適宜更新していくことにより, 各
に対して計算量
で求められる.
以上から, が答えであり, 計算量も
時間で求まる. また, 第2項の部分を工夫することにより,
時間でも求めることができる,