モラトリアムライフ

自由を求めて

精進記録 : Educational Codeforces Round #55 E. Increasing Frequency

問題概要

n 個の正の整数からなる数列 \{a_{i} \}_{i = 1}^{n} が与えられる.
このとき, 区間 \left[ l, r \right] \, \left( \, \subseteq \left[1, n \right] \, \right) と整数 k (負の数でも, 0でもよい) をそれぞれ好きに選んで, 区間上の各 a_{i} \, \, \left( i \in \left[ l, r \right] \right) に対して k を加えるという操作を1回だけ行う. (いわゆる区間加算)

このとき, 最大でいくつ 数列の値を与えられる正の整数 c に等しくすることが可能かを求めよ.

制約

  • 1 \leq n, \, c \leq 5 \cdot 10^{5}
  • 1 \leq a_{i} \leq 5 \cdot 10^{5} \, \, \left( \, \forall \, i \, \in \, \left[l, r \right] \right) \,

codeforces.com

考察

まず, はじめに浮かぶのは選ぶ区間の全探索だろう. しかし当然これは区間を走査するだけで O(n^{2}) かかってしまい間に合わない. そこで, 一旦操作を観察することにする.
もし, 区間 [l, r] に整数 k を加えたとき, k に等しくなるものは, 元の数列 \{a_{i} \}_{i = 1}^{n} で 区間 [0, l )上で c と等しくなるもの, 区間 [l, r] 上で c - k に等しくなるもの, 区間 (r, l ] 上で c に等しくなるもの の3つに分けられる. すると定式化しやすそうなので定式化してみることにする. (ただし, 区間は半開区間で扱うことにする)

S_{r}(a) := \text{半開区間 } [0, r) \text{ 上で整数 } a \text{ に等しいものの個数}

と 各整数 aに対しての出現回数の累積和を表すことにすると 半開区間 [l, r) に対して 整数 k を加えた操作のときに c に等しいものの個数は

\begin{aligned} Count \, (l, r) &= \text{区間 }[0, l) \text{上の } c \text{ の個数} + \text{区間 }[l, r) \text{上の } c - k \text{ の個数} + \text{区間 }[r, n) \text{上の } c \text{ の個数}\\ &= (S_{l}(c) - S_{0}(c))+ ( S_{r}(c-k) - S_{l}(c -k) ) + (S_{n}(c) - S_{r}(c))\\ &= ( \, S_{l}(c) - S_{l}(c - k) \, ) + ( \, S_{r}(c - k) - S_{r}(c) \, ) + ( S_{n}(c) - S_{0}(c)) \\ \end{aligned}


と, ( k の選び方には依存するが ) 目的関数 Count\, (l, r) を ( \, l \, \text{に依存する部分}) + ( \, r \, \text{に依存する部分}) + ( \text{定数部}) に分解することができた.
これにより, 最適性を満たす区間のみを探索することにより探索範囲を狭めることができることができる.
ここで, 区間の右端を全探索することを考える. このとき, k の値 すなわち c - k の値を定めると選ぶべき左端は即座に定まる. では, どのような値を選ぶべきか. それは明らかに 右端の値 を c に変えるような値である. (そうでないと, 右端を左に1つずらすことで 悪化させずに同様の問題に帰着でき, もし右端が c の値と等しければより良い値を得られるからである)
したがって, l, \, k は r により定まっているので, 各整数 について l に依存する部分の最適値を適切に更新していくことによって, 時間計算量 O(n), 空間計算量 O(max\, (c, \, a_{max})) で計算することができた.

実装例

codeforces.com