[AtCoder] CODE THANKS FESTIVAL 2018 C – Pair Distance

問題

方針

交流コスト

交流コストを \( c \) と置くと、

\[c = \sum_{i = 1}^{N – 1} \sum_{j = i + 1}^{N} |x_j – x_i|\]

となります。このシグマの計算回数は、\( \dfrac{N(N – 1)}{2}\) となり、\( N \) 人から \( 2 \) 人選ぶときの組み合わせに対応していることが分かります。

ここで、\( x_i \) は並び替えても交流コストには影響しないので、昇順になるように並び替えると、\( x_i \leq x_{i+1} \) が成り立つので、上式は、

\[c = \sum_{i = 1}^{N – 1} \sum_{j = i + 1}^{N} (x_j – x_i)\]

のように、絶対値が外せます。

交流コストの計算

交流コストは、次の累積和を用いて計算することができます。\( x_i \) の累積和を \( S_i \) とすると、

\[ S_i = x_1 + x_2 + \cdots + x_i\]

のように表せます。これを用いて、交流コスト \( c \) は、

\[
\begin{eqnarray}
c &=& \sum_{i = 1}^{N – 1} \sum_{j = i + 1}^{N} (x_j – x_i)\\
&=& (x_2 – x_1) + (x_3 – x_1) + \cdots + (x_N – x_1) \\
&+& (x_3 – x_2) + (x_4 – x_2) + \cdots + (x_N – x_2) \\
&\vdots&\\
&+& (x_N – x_{N-1})\\
&=& (S_N – S_1) – (N – 1)x_1\\
&+& (S_N – S_2) – (N – 2)x_2\\
&\vdots&\\
&+& (S_N – S_{N – 1}) – (N – (N – 1))x_{N-1}
\end{eqnarray}
\]

と計算することができます。

コード

提出したコード

交流コストの計算