AtCoderログ：0060 - ABC 156 C

問題

問題文

数直線上に $N$ 人の人が住んでいます。
$i$ 番目の人が住んでいるのは座標 $X_i$ です。
あなたは $N$ 人全員が参加する集会を開くことを考えています。
集会は数直線上の任意の 整数値の座標 で開くことができ、座標 $P$ で集会を開くとき、$i$ 番目の人は集会に参加するために $(X_i−P)^2$ の体力を消費します。
$N$ 人が消費する体力の総和としてありえる値の最小値を求めてください。

制約

・入力は全て整数である。
・$1 \le N \le 100$
・$1 \le X_i \le 100$

収録されている問題セット

• [BfB-E](AtCoder Problems Boot camp for beginners Easy 100) #002

回答

回答1 (AC)

考えられる全ての $P$ の値に対して $\sum_{i=1}^N (X_i-P)^2$ を求め、その最小値を求めれば良いでしょう。ここで $1 \le X_i \le 100$ より $1 \le P \le 100$ となる (例えば $P=0$ は $P=1$ に比べ全員にとって遠くなるので、$P=0$ で最小値になることはない。同様にして $P<0$, $100<P$ で最小値になることはない)。コードは以下のようになりました。

abc156c-1.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;
  cin >> n;

  vector<int> x(n);
  for ( int i=0; i<n; i++ ) {
    cin >> x.at(i);
  }

  int dmin = INT_MAX;
  for ( int p=1; p<=100; p++ ) {
    int sum = 0;
    for ( int i=0; i<n; i++ ) {
      sum += pow(x.at(i)-p,2);
    }
    dmin = min(dmin,sum);
  }

  cout << dmin << endl;
}

計算量を考えると、$P$ の値は 100 通りで、それぞれの $P$ の値に対して $N$ 回の繰り返しを行うので、全体の計算量は $O(100N)=O(N)$ となります。

回答2 (AC)

少し数学的に考察すると、最小値となる $P$ の値を直接求めることができます。$X_1,X_2,\dots,X_N$ が与えられたとき、設問は、関数
$$
D(P) = \sum_{i=1}^N (X_i-P)^2
$$
の最小値を求めよというものでした。ここで式変形をすると

\begin{align}
 D(P) &= \sum_{i=1}^N (X_i-P)^2 \\
      &= (X_1^2+\dots+X_N^2)-2(X_1+\dots+X_N)P+NP^2 \\
      &= N\biggl(P-\frac{X_1+\dots+X_N}{N}\biggr)^2 + A
\end{align}

となります。ここで $A=(X_1^2+\dots+X_N^2)-\frac{(X_1+\dots+X_N)^2}{N^2}$ は $P$ とは無関係な値です。つまり関数 $D(P)$ は $P$ に関する二次関数で、$P=\frac{X_1+\dots+X_N}{N}$ のときに最小値 $A$ をとることがわかります。これは、最小値になる $P$ は $N$ 人の家の座標の平均、つまり全員の家の重心になることを意味していて、自然な結果になっています。

設問では $P$ は整数値に限定されているので、関数 $D(P)$ が最小値をとるのは $P=\frac{X_1+\dots+X_N}{N}$ に最も近い整数値となります。よって、(小数として) $(X_1+\dots+X_N)/N$ を四捨五入した値が求める $P$ の値となります。
なお、小数 $x$ を四捨五入した値を $\lceil x \rfloor$ とかくことがあります (Round 関数)。このとき $\lceil x \rfloor = \lfloor x+0.5 \rfloor$ という関係式が成立するので、Round 関数は床関数 (小数点以下を切り捨てる関数) で表すことができます。

コードは以下のようになりました。$X_i$ の値を受け取る際に、2種類の和 ${\rm Sum}_1=X_1+...+X_N$ と ${\rm Sum}_2=X_1^2+...+X_N^2$ を計算しておくと、$N$ に関するループは1回で済みます。

abc156c-2.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;
  cin >> n;

  vector<int> x(n);
  int sum1 = 0, sum2 = 0;
  for ( int i=0; i<n; i++ ) {
    cin >> x.at(i);
    sum1 += x.at(i);
    sum2 += x.at(i)*x.at(i);
  }

  int p = floor((float)sum1/n+0.5);
  int dmin = sum2 - 2*sum1*p + n*p*p;

  cout << dmin << endl;
}

調べたこと

AtCoder の解説 → ユーザ解説

回答1と同じ方針でした。
9

AtCoder の解説 → 全体の解説

こちらも回答1と同じ方針でした。

リンク

前後の記事

• 前の記事 → AtCoderログ：0059 - AGC 027 A
• 次の記事 → AtCoderログ：0061 - AGC 012 A