Plant seeds

路頭に迷ってしまいそうな大学院生が、どこかに書かなければ忘れてしまいそうな大切なことをここに残していきます。

Noelちゃんと星々 | yukicoder No.609

最近就活でプログラミングの試験がボロボロになって悔し涙を垂らしたくらいなので競プロをはじめることにしまして、そこで自分の専門分野に近すぎる問題が出たので解説しようと思います。

No.609 Noelちゃんと星々 - yukicoder

与えられた点 {Y_i}をある高さ Pに揃えると全ての点を動かすのに必要な距離が最小、つまり与えられた点とその高さ Pの間の距離の総和が最小になる基準点 Pを見つけるということなので、この問題は次のように書けます。

 \sum_{i=1}^N |Y_i - P| Pに関しての最小値

ここでの最適点 Pは一般に {Y_i}メジアンであることが知られているので、最適点 Pメジアンを使って解けばよいです。

from statistics import median
N = int(input())
Y = list(map(int, input().split()))
P = median(Y)
print(int(sum([abs(y - P) for y in Y])))

ちなみに僕の研究分野はL1誤差最小化です。