ABC156 C - Rally を解いた

文章通り入れてみた。別に sort しなくても
良いと思うけど。。。

abc156c.py

N = int(input())
X = list(map(int,input().split()))
X.sort()

ans = float("inf")
for i in range(1,101):
    score = 0
    for j in range(N):
        score += (X[j]-i)**2
    ans = min(score,ans)

print(ans)#28ms

別解として面白いものを見つけた。
座標として有効なのは X の平均値とあたりを付ける場合。

abc156c.py

def solv():
    N = int(input())
    X = list(map(int,input().split()))
    
    canditates = [sum(X)//N,sum(X)//N+1]
    a,b = 0,0
    for x in X:
        a += (x-canditates[0])**2
        b += (x-canditates[1])**2
    if a > b:
        print(b)
    else:
        print(a)
solv()#28ms

しかし、平均値も 2.01 なのか 2.91 なのかで、
妥当な平均値は 2 の場合、3の場合と別れる。

それぞれの場合で体力の消耗を合算していき、
小さい方を出力する。

なぜ平均値?
例えば、問題では 2 点が与えられたとする。
その場合の、それぞれの体力消耗は以下で求まる

(x0-p)^2 = x0^2 -2x0p+p^2
(x1-p)^2 = x1^2 -2x1p+p^2

上記を合算し、p について整理をすると

2{p^2 - {(x0+x1)/2}p + (x0^2+x1^2)/2}

となる。お気づきだと思うが
上記を p に関する二次関数と判断すると

p = (x0+x1)/2 の時、p の関数は最小値になることが分かる

(x0+x1)/2 って与えられた 2 点の平均ですよね?(笑)

何も考えず、雰囲気で for 文を回すのと
数式で考えて for 文を回すのでは問題に対するスタンスが
全く違うようです。

処理時間は殆ど変らないけど(笑)