yukicoder No.731 等差数列がだいすき

この記事は、yukicoder No.731 等差数列がだいすき の解説です。

\(0\)-indexed とする。\(\sum\) はすべて \(\displaystyle\sum_{i=0}^{N-1}\) の略として用いる。

最小二乗法は分からないので次のように式変形する。

\(\sum(a_i-b_i)^2\\ =\sum(a_i-(b_0+di))^2\\ =\sum(a_i^2+b_0^2+d^2i^2-2a_ib_0+2b_0di-2a_idi)\\ =Nb_0^2+(\sum2i)b_0d+(\sum i^2)d^2+(\sum-2a_i)b_0+(\sum-2a_ii)d+(\sum a_i^2)\)

これにより、\(b_0\) と \(d\) についての \(2\) 変数関数が得られた。これを \(f(b_0,d)\) とする。

一般に \(2\) 変数関数 \(F(x,y)\) が \((x,y)=(a,b)\) で極値をとるとき、\(F_x(a,b)=0\) かつ \(F_y(a,b)=0\) が成り立つ（逆は成り立つとは限らない）。
（ここで、\(F_x\) は \(x\) 偏微分、\(F_y\) は \(y\) 偏微分）

ジャッジ形式を見ると、出力が一意に定まることが分かるので、\(f(b_0,d)\) には極値があり、それを求めればよいことが分かる。
\(b_0,d\) のそれぞれで偏微分すると、どちらも \(b_0^2,b_0d,d^2\) の項が消え、\(b_0,d\) の項と定数項だけが残るので、あとは普通に \(2\) 元 \(1\) 次連立方程式 \(\begin{eqnarray} \left\{ \begin{array}{l} f_{b_0}(b_0,d)=0\\ f_d(b_0,d)=0 \end{array} \right. \end{eqnarray}\) を解けば、極値をとる \(b_0,d\) の値が求まる。