はじめに
このシリーズではレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】でまとめられている100問をPythonで解いています。
問題
Square869120Contest #6 B - AtCoder Markets
ポイント
最適な入口と最適な出口について、どのようなものかを考えてみます。
買い物客は入口→A→B→出口の順にマスを通っていくので、入口はなるべくAに近いほうが良いし、出口はなるべくBに近いほうが良さそうです。
買い物客がもし1人ならば、入口=A, 出口=Bと置けば最適解ですが、買い物客が複数いる場合は入口=全てのAの中央値、出口=全てのBの中央値とすることで最適解を得ることができます。
全てのAの中央値は
①全てのAを昇順に並べる
②Aの全体数を2で割った数をXと置いて、
(i)Aの全体数が奇数の場合：X+1番目 例：(1,3,4,5,9) なら中央値は4
(ii)Aの全体数が偶数の場合：X番目,もしくはX+1番目 例：(1,3,4,6) なら中央値は3,または4
の値を取得することで求められます。
※中央値 != 平均値なので注意してください。
※実装では奇数でも偶数でもX+1番目を採用することとし、len(list_A) // 2の部分で中央値の
インデックスを取得しています。
コード
def main():
N = int(input())
list_A = []
list_B = []
for i in range(N):
A, B = map(int, input().split(" "))
list_A.append(A)
list_B.append(B)
list_A.sort()
list_B.sort()
s = len(list_A) // 2 # Aの中央値のインデックス
t = len(list_B) // 2 # Bの中央値のインデックス
ans = 0
for i in range(N):
ans += abs(list_A[s] - list_A[i]) # Aの中央値(入口)とAの距離
ans += abs(list_A[i] - list_B[i]) # AとBの距離
ans += abs(list_B[t] - list_B[i]) # Bの中央値(入口)とBの距離
print(ans)
if __name__ == '__main__':
main()
