https://algo-method.com/tasks/706
問題文より、
f(x)=\frac{1}{N}\sum_{i=0}^{N-1}{(A_i-x)^2}
この f(x) を最小にする x について考えてみます。
(A_i-x)^2={A_i}^2-2A_ix+x^2 より
\begin{aligned}
f(x)&=\frac{1}{N}\sum_{i=0}^{N-1}{(A_i-x)^2}\\
&=\frac{1}{N}\sum_{i=0}^{N-1}{{A_i}^2}-\frac{1}{N}\sum_{i=0}^{N-1}{2A_ix}+\frac{1}{N}\sum_{i=0}^{N-1}{x^2}
\end{aligned}
ここで
\begin{aligned}
\frac{1}{N}\sum_{i=0}^{N-1}{x^2}&=\frac{N}{N}x^2=x^2\\
-\frac{1}{N}\sum_{i=0}^{N-1}{2A_ix}&=-\frac{2x}{N}\sum_{i=0}^{N-1}{A_i}
\end{aligned}
であるから、x について整理すると
f(x)=x^2-\frac{2x}{N}\left(\sum_{i=0}^{N-1}{A_i}\right)+\frac{1}{N}\left(\sum_{i=0}^{N-1}{{A_i}^2}\right)
若干見づらいので、
\begin{aligned}
\overline{A}&=\frac{1}{N}\sum_{i=0}^{N-1}{A_i}\\
\overline{A^2}&=\frac{1}{N}\sum_{i=0}^{N-1}{{A_i}^2}
\end{aligned}
とそれぞれ表記することにしましょう。
すると以下のようになります。
\displaystyle f(x)=x^2-2x\overline{A}+\overline{A^2}
このまま平方完成すると
\begin{aligned}
f(x)&=x^2-2x\overline{A}+\overline{A^2}+{\overline{A}}^2-{\overline{A}}^2\\
&=x^2-2x\overline{A}+{\overline{A}}^2+\overline{A^2}-{\overline{A}}^2\\
&=(x-\overline{A})^2+\overline{A^2}-{\overline{A}}^2
\end{aligned}
以上から、f(x) は x=\overline{A} のときに最小値をとることがわかります。
したがって、
\underset{x\in\mathbb{R}}{\argmin}f(x)=\overline{A}
が成り立ちます。
ところで、\overline{A} は定義より \displaystyle \overline{A}=\frac{1}{N}\sum_{i=0}^{N-1}{A_i} だったのですが、これは A_0, A_1, A_2, ... の平均値を計算していることに気づきます。
よって、問題を解くには平均値を計算すれば良いことがわかりました。
Discussion