きっかけ
AtCoder Beginner Contest 043 C - いっしょ / Be Together でこんな問題に出くわしました。
###問題文
$N,$個の整数$,a_1,a_2,..,a_N,$が与えられます。えび君はこれらを書き換えて全て同じ整数にしようとしています。各$a_i(1\leqq i\leqq N)$は高々一回しか書き換えられません(書き換えなくても良い)。整数$,x,$を整数$,y,$に書き換えるとき、コストが$,(x-y)^2$かかります。仮に$a_i=a_j(i\neq j)$だとしても、ひとつ分のコストで同時に書き換えることは出来ません。えび君が目的を達成するのに必要なコストの総和の最小値を求めてください。
要は「$,\sum_{k=1}^n (a_k-y)^2,$の最小値を求めよ$,(y,$は整数$),$」ということですが、これって分散を求める公式
{s_x}^2=\frac{1}{n}\sum_{k=1}^n (x_k-\bar{x})^2
から$,\frac{1}{n},$を除いたものとほぼ同じ式ですよね。ということで$,y,$には$,a_1,a_2,..,a_N,$の平均$,\bar{a},$が入りそうですが、それは本当なのでしょうか。そして、そういえば何故分散の公式は偏差、つまり「データと平均の差」を2乗しているのでしょうか。
とりあえず問題を解いてみましょう。
解いてみる
問題
変量 $x$ の $n$ 個のデータ $x_1,x_2,..,x_n $ について、
\sum_{k=1}^n (x_k-p)^2=(x_1-p)^2+(x_2-p)^2+…+(x_n-p)^2
の値が最小となるような実数 $p$ の値を求めよ。
解答例
\begin{align}
\sum_{k=1}^n (x_k-p)^2&=(x_1-p)^2+(x_2-p)^2+…+(x_n-p)^2 \\
&=({x_1}^2-2x_1p+p^2)+({x_2}^2-2x_2p+p^2)+…+({x_n}^2-2x_np+p^2) \\
&={np^2}-2(x_1+x_2+…+x_n)p+({x_1}^2+{x_2}^2+…+{x_n}^2) \\
&=n\left(p^2-\frac{2(x_1+x_2+…+x_n)}{n}p\right)+({x_1}^2+{x_2}^2+…+{x_n}^2) \\
&=n\left(p^2-2\bar{x}p\right)+({x_1}^2+{x_2}^2+…+{x_n}^2) \\
&=n(p-\bar{x})^2-n\bar{x}^2+({x_1}^2+{x_2}^2+…+{x_n}^2) \\
\end{align}
したがって、$\sum_{k=1}^n (x_k-p)^2$ は$\ p=\bar{x}\ $のとき最小値をとる。
合ってた
ということで、$,y=\bar{a},$にすればよいことが確実になりました。なお、今回の問題では$,y,$は整数という制約があるため、$,y,$には$,\bar{a},$の小数点以下を四捨五入したものが入ります。あとは線形探索で$,(a_1-y)^2,(a_2-y)^2,,…,,(a_N-y)^2,$を順々に計算し、合計を求めればOKです。
分散の公式がデータと平均の差を2乗しているのは、もしかすると得られる値が最小になるからなのかもしれませんね。あくまで憶測ですが。
ところでえび君って誰なんでしょうか。以上です。