ABC156 C問題 Rallyの解説

ABC156 C問題 Rallyを解説します。

atcoder.jp

問題

数直線上に N 人の人が住んでいます。
i 番目の人が住んでいるのは座標 です。
あなたは N 人全員が参加する集会を開くことを考えています。

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

解き方のイメージ

NとXの制約は最大で100です。
集会を開く座標の範囲も最悪のケースで1から100までの間になります。
集会を開く座標Pを固定した時に、Pとそれぞれの住人の座標の差分の二乗の合計を求めるのも最大で100回です。
なので全探索しても計算量は最大で10000回なので、余裕で解けることがわかります。

Pの探索する範囲は、Xの最小値と最大値の間でよいので、その範囲でループさせます。

全体のコードはこのようになりました。

N = int(input())

# ソートしておいて、Xの最小値と最大値を取りやすくする
x_arr = sorted(list(map(int, input().split())))
# 答えの初期値はすごく大きい数にする
ans = 10**9 + 7
# Xの最小値と最大値の間でPを変動させる
for p in range(x_arr[0], x_arr[-1] + 1):
    total = 0
    for x in x_arr:
        total += (x - p) ** 2
    # 累積和を比較して最小のものを答えにする
    ans = min(ans, total)
print(ans)