【ABC156 C】「Rally」を解く【Python3】

abc156c

コンテスト一覧へ

 

数直線上のN人が座標Pで集会を開くとき、N人が消費する体力の総和の最小値を求める問題です。

i番目の人は座標Xi に住んでおり、集会に参加するために、(Xi−P)2 の体力を消費します。

集会は数直線上の「整数値の座標」で開かれるため、この整数値を愚直にすべて試しても解くことができます。

提出
n = int(input())
xi = list(map(int, input().split()))

mi = min(xi)
ma = max(xi)
ans = 1000000

for i in range(mi, ma + 1):
    num = 0
    for j in range(n):
        num += (xi[j] - i) ** 2
    ans = min(ans, num)

print(ans)

Xiは、「1〜100」までの整数なので、この範囲のどこかで集会を開くことになります。

(この範囲以外では、体力の総和が大きくなることが予測できるかと思います)

上記では、Xiの最小値と最大値をとってしまいましたが、取らなくても間に合いますね。

for文を用いて、Pを仮定し、すべての (Xi−P)2 を足し合わせ、「ans」と比較して小さい方を「ans」に入れるという処理を繰り返します。

ansの初期値には適当に大きい数字を入れています。

【ABC156】解説記事リスト

コンテスト一覧に戻る

コメントを残す

メールアドレスが公開されることはありません。