[AtCoder] CODE THANKS FESTIVAL 2018 C – Pair Distance

2019年6月15日

問題

方針

交流コスト

交流コストを \( 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}
\]

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

コード

提出したコード

交流コストの計算

  vector<ll> x(N);
  for (int i = 0; i < N; i++) {
    cin >> x[i];
  }
  sort(x.begin(), x.end());;
  ll y[N + 1]{};
  for (int i = 0; i < N; i++) {
    y[i + 1] += y[i] + x[i];
  }
  ll cost = 0;
  for (int i = 0; i < N - 1; i++) {
    cost += y[N] - y[i + 1] - (N - i - 1) * x[i];
  }
  cout << cost << "\n";