137AC - ABC102C: Linear Approximation

ABC0102-C (300 points)

問題

長さ $N$ の整数列 $A$ があるとき, 以下を最小にするような整数 $b$ とそのときの最小値を求める.
$\begin{equation} \begin{split} \sum_{i = 1}^{N} |A_i - (b + i)| \end{split} \end{equation}$

$1 \leq N \leq 2 * 10^5$
$1 \leq A_i \leq 10^9$
入力は全て整数

方針

$\sum_{i = 1}^{N} |A_i - b|$ が, $b = median(A)$ のときに最小値を取ることが示せれば, $A_i \to A_i - i$ と置き換えて中央値を取ることで最小値を計算可能.

証明

$A$ は昇順にソートされていると仮定し, $A$ の中央値を $A_m, m = \lceil \frac{N}{2} \rceil$ とする.
任意の $x > 0$ に対して,
$\begin{equation} \begin{split} \sum_{i = 1}^{m} |A_i - A_m - x| = \sum_{i = 1}^{m - 1} |A_i - A_m| + m x \end{split} \end{equation}$
と,
$\begin{equation} \begin{split} \sum_{i = m + 1}^{N} |A_i - A_m - x| &\geq \sum_{i = m + 1}^{N} |A_i - A_m| - (N - m) x \\ &\geq \sum_{i = m + 1}^{N} |A_i - A_m| - m x \end{split} \end{equation}$
を考えると,
$\begin{equation} \begin{split} \sum_{i = 1}^{N} |A_i - A_m - x| &\geq \sum_{i = 1}^{N} |A_i - A_m| \\ \end{split} \end{equation}$
となる. $x < 0$ の場合も同様にすることで, $\sum_{i = 1}^{N} |A_i - b|$ が, $b = median(A)$ のときに最小値を取ることが示せる.

from statistics import median_low

# input
N = int(input())
A = list(map(int, input().split()))

for i in range(N):
    A[i] = A[i] - (i + 1)

b = median_low(A)
ans = 0

for i in range(N):
    ans += abs(A[i] - b)

print(ans)