【競プロ】過去問精選100問「Square869120Contest #6 B - AtCoder Markets」解法
Free-PhotosによるPixabayからの画像

はじめに

このシリーズではレッドコーダーが教える、競プロ・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()
おすすめの記事