ヤマカサのプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

AtCoder Beginner Contest 102 C - Linear Approximation

Java AtCoder

問題

C - Linear Approximation

タイトルが線形近似ということで、最小二乗法とかを連想しますね。

調べてみると、割と有名な問題のようですね。大学受験の問題でも出されたことがあるようです。

考え方

この問題を一般化すると、 $f(x)$ を最小化する整数 $x$ を求めよという問題になります。

$f(x) = |a_1 - x| + |a_2 - x| + \cdots + |a_n - x|$

$1 \leq a_1 \leq a_2 \leq \cdots \leq a_n$

$S_i = a_1 + a_2 + \cdots + a_i$

とします。

場合分け

絶対値を外すために場合分けをして考えます。

$1 \leq x \leq a_1$ のとき

$f(x) = (a_1 - x) + (a_2 - x) + \cdots (a_n - x)$

$= S_n - nx$

となり、最小値は、

$f(a_1) = S_n - na_1$

となります。

$a_1 \lt x \leq a_2$ のとき

$f(x) = - (a_1 - x) + (a_2 - x) + \cdots (a_n - x)$

$= S_n - 2S_1 - (n - 2)x$

となり、最小値は、

$f(a_2) = S_n - 2S_1 - (n - 2)a_2$

$= S_n - 2a_1 - (n - 2)a_2$

$= S_n - 2(a_2 - a_1) - na_2 \leq S_n - na_1$

となるので、 $f(a_1)$ 以下となります。この操作を続けていくと、何かわかりそうですね。

一般化すると、

$a_{k - 1} \lt x \leq a_k$ のとき

$f(x) = - (a_1 - x) - (a_2 - x) - \cdots - (a_{k - 1} - x)+ (a_k - x) +\cdots + (a_n - x)$

$= S_n - 2S_k - (n - 2k)x$

となります。

ここで、次の式を考えます。

$f(a_{k - 1}) - f(a_k) = S_n - 2S_{k - 1} - (n - 2(k -1))a_{k - 1} -(S_n - 2S_k - (n - 2k)a_k)$

$= 2(S_k - S_{k - 1}) - (n - 2(k - 1))a_{k - 1} + (n - 2k)a_k$

$= (n - (2k - 1))(a_k - a_{k - 1})$

したがって、

$f(a_{k - 1}) - f(a_k) = (n - (2k - 1))(a_k - a_{k - 1})$

において、

$a_k - a_{k - 1} \geq 0$

であることに注意すると、

$n - (2k - 1) \geq 0$ のとき

$f(a_{k - 1}) \geq f(a_k)$

なので、 $k = \dfrac{n + 1}{2}$ のとき最小となります。

追記(2/2)

このとき、 $1 \leq k \leq \dfrac{n + 1}{2}$ 、 $a_{k - 1} \lt x \leq a_k$ であり、

$f(a_1) \geq f(a_2) \geq \cdots \geq f(a_k)$

となるので、 $x$ の最大値をとることで、 $f(x)$ は最小化されます。よって $k$ を大きくすることで $x$ の取れる値が大きくなるので、 $x = a_k \ (k = \dfrac{n + 1}{2} )$ のときが $f(x)$ を最小化します。

(追記終了)

$n - (2k - 1) \leq 0$ のとき

$f(a_{k - 1}) \leq f(a_k)$

なので、 $k = \dfrac{n + 1}{2}$ のとき最小となります。

追記(2/2)

このとき、 $\dfrac{n + 1}{2} \leq k \leq n$ であり、

$f(a_k) \leq f(a_{k + 1}) \leq \cdots \leq f(a_n)$

となるので、 $k$ の値を小さくすることで、 $f(a_k)$ は小さくなります。

$x$ の範囲を $a_{k - 1} \lt x \leq a_k$ としてしまっているので、 $x = a_{k - 1}$ と取れませんが、等号付き不等号としても一般性を失いません。

したがって、 $k = \dfrac{n + 1}{2}$ のとき、 $x$ の最小値 $x = a_k$ が $f(x)$ を最小化します。

(追記終了)

まとめ

したがって、中央値が最小値となります。中央値は偶数のとき、中央値が2つあるので、それの平均値をとる必要があるんですが、この問題では平均を取らなくても大丈夫です。

$n = 2m$ のとき

$f(x) = |a_1 - x| + |a_2 - x| + \cdots + |a_{2m} - x|$

とします。

$f(a_m) = S_{2m} - S_m$

$f(a_{m + 1}) = S_{2m} - S_{m +1} - (2m - 2(m + 1))a_{m + 1}$

$= S_{2m} - S_{m}$

となり、同じ値になります。