問題概要
問題ページ
-
-
C - Rally
問題ページへ移動する
問題文
数直線上に \(N\) 人の人が住んでいます。
\(i\) 番目の人が住んでいるのは座標 \(X_i\) です。
あなたは \(N\) 人全員が参加する集会を開くことを考えています。
集会は数直線上の任意の 整数値の座標 で開くことができ、座標 \(P\) で集会を開くとき、\(i\) 番目の人は集会に参加するために \((X_i - P)^2\) の体力を消費します。
\(N\) 人が消費する体力の総和としてありえる値の最小値を求めてください。
制約
- 入力は全て整数である。
- \(1 \leq N \leq 100\)
- \(1 \leq X_i \leq 100\)
問題の考察
\(X_i\)の最大値と最小値の外側に解が存在しますが、この外側に解が存在すると仮定してみましょう。
解となる\(P\)が\(0\)だと仮定してみます。
解の範囲を考える
- \(P=1\)の時
- \((X_i - P)^2\)
- 解が\(0\)だとすると\(P=1\)より
- \((X_i - (P-1))^2\)
- \(=(X_i +1- P)^2\)
- \(X_i\)は\(1 \leq X_i \leq 100\)から
- \((X_i - P)^2 \lt (X_i - (P-1))^2\)
これより答えとなる\(P\) の値は\(X_i\)の最大値と最小値の間に存在することが分かり、制約が緩く\(1≤X_i≤100\)となっていますので全検索してしまっても問題ないです。
\(1≤X_i≤100\)と\(1 \leq N \leq 100\)から、最大計算量は\(O(100 \times 100)\)で\(10,000\)となります。
\(1\)から\(100\)の値を全検索してもpythonで十分に間に合います。
ACコード
import sys
def solve():
readline = sys.stdin.buffer.readline
mod = 10 ** 9 + 7
n = int(readline())
x = list(map(int, readline().split()))
x.sort()
mt = 10 ** 10
for i in range(x[0], x[-1] + 1):
t = 0
for v in x:
t += (v - i) ** 2
mt = min(mt, t)
print(mt)
if __name__ == '__main__':
solve()