コンテストでの時間切れや解けなかった過去問を振り返って供養していく

問題

Difficulty: 2143 (記事作成時点)

供養

解法

ある最適解は、任意の $1 \le i \lt N$ について $B_{i} = B_{i + 1}$ もしくは $C_{i} = C_{i + 1}$ の少なくとも一方が成り立っている
- ある $1 \le i \lt N$ について $B_{i} \lt B_{i + 1}$ かつ $C_{i} \gt C_{i + 1}$ であるような解の数列 $B, C$ があったとする
- このとき、以下のように作成した数列 $B^{'}, C^{'}$ を考える
  - $B_{i} \lt 0$ ならば $j \le i$ について $B_{j}$ を $1$ 増加、$C_{j}$ を $1$ 減少させる
  - $B_{i + 1} \gt 0$ ならば $j \ge i + 1$ について $B_{j}$ を $1$ 減少、$C_{j}$ を $1$ 増加させる
- 各 $1 \le i \le N$ について $B^{'}_{i} + C^{'}_{i} = A_{i}$ は維持されている
- $B_{i} \lt 0$ のとき、$\sum_{j = 1}^{i}|B^{'}_{j}| = \sum_{j = 1}^{i}|B_{j}| - i$ であり、$\sum_{j = 1}^{i}|C^{'}_{j}| \le \sum_{j = 1}^{i}|C_{j}| + i$ である
  - $B_{j} \lt 0$ なので $|B^{'}_{j}| = |B_{j} - 1| = |B_{j}| - 1$
  - $|C^{'}_{j}|$ は $C_{j}$ の値によって以下のようになる \begin{align} |C^{'}_{j}| = \begin{cases} |C_{j}| + 1 & \mathrm{if}\;C_{j} \ge 0 \\ |C_{j}| - 1 & \mathrm{if}\;C_{j} \lt 0 \end{cases} \end{align}
- $B_{i + 1} \gt 0$ のとき、$\sum_{j = i + 1}^{N}|B^{'}_{j}| = \sum_{j = i + 1}^{N}|B_{j}| - (N - i)$ であり、$\sum_{j = i + 1}^{N}|C^{'}_{j}| \le \sum_{j = 1}^{N}|C_{j}| + (N - i)$ である
- よって、どちらの場合においても $\sum_{j}(|B^{'}_{j}| + |C^{'}_{j}|) \le \sum_{j}(|B_{j}| + |C_{j}|)$ であることから、同等以上によい解である $B^{'}, C^{'}$ が存在する
- これを繰り返すことで、任意の $1 \le i \lt N$ について $B_{i} = B_{i + 1}$ もしくは $C_{i} = C_{i + 1}$ の少なくとも一方が成り立つような $B, C$ まで局所最適化を実行できる
上記の性質を踏まえると、$i \gt 1$ について $B_{i} = B_{i - 1} + \max(A_{i} - A_{i - 1}, 0), C_{i} = C_{i - 1} + \min(A_{i} - A_{i - 1}, 0)$ であるような数列が存在する
- $A_{i} \gt A_{i - 1}$ のとき、$B_{i} = B_{i - 1}$ だと $C_{i} \gt C_{i - 1}$ となってしまうため、$B_{i} = B_{i} + (A_{i} - A_{i - 1}), C_{i} = C_{i - 1}$
- $A_{i} \lt A_{i - 1}$ のときも同様に考えることができる
- $A_{i} = A_{i - 1}$ ならば変化させる必要なし
また、$C_{1} = A_{1} - B_{1}$ であることから上記の性質をもった数列は $B_{1}$ を決めるとすべての値を一意に決めることができる
よって、$|B_{i}|, |C_{i}|$ は $B_{1}$ を用いて $|B_{1} - d|$ の形式で表現できる
上記より、$\sum_{i}(|B_{i}| + |C_{i}|)$ を最小化する問題は $2N$ 個の $d_{j}$ が与えられたときに $\sum_{j}|B_{1} - d_{j}|$ を最小化する $B_{1}$ を選ぶ問題と等しくなる
- その問題については $B_{1}$ が $B_{1}, d_{1}, \dots, d_{2N}$ の $2N$ 個のなかで中央値となるようにすればよい
選んだ $B_{1}$ から $\sum_{i}(|B_{i}| + |C_{i}|)$ を計算して出力すればよい