競プロ典型90問 ★3 014 - We Used to Sing a Song Together コード解説

はじめに

お疲れ様です。もう12月も半ばになり、年末年始の話をすることも増えてきましたね。
前回、本日から動的計画法（DP）の強化週間にしようと申し上げていたのですが、ちょっとトラブルがあって勉強が進まなかったので、競プロ典型90問の★3問題をやっていこうと思います。
本日も頑張っていきましょ～

競プロ典型90問

atcoder.jp

014 - We Used to Sing a Song Together

014 - We Used to Sing a Song Together

AGCはたぶん「Atcoder Grand Contest」のことだと思います。めちゃくちゃ難易度が高く一流プログラマの方々がしのぎを削っているコンテストです。「AGC街道に住む小学生は性格が悪い」っていうのは意味深ですね。

小学生と同じ数だけ（N）小学校があって、それぞれが別の小学校に通うという条件のもと、それぞれの家から学校までの距離を最小化します。

結論から言えば、「家の場所と学校の場所をソートして、家のインデックスが対応する学校に行く」というのが、最も距離の和が短くなる通い方だといえます。コードは短く、以下のようになります。

n = int(input())
a_list = list(map(int, input().split(" ")))
b_list = list(map(int, input().split(" ")))
 
a_list.sort()
b_list.sort()
ans = 0
for i in range(len(a_list)):
    ans += abs(a_list[i] - b_list[i])
print(ans)

おわりに

今回は解説もコードもかなり短くなりましたね。どちらも短いほうが美しいですよね！（コードはともかく解説の手を抜いたわけではないですよ…！）
明日はDPできるといいな～ お疲れ様でした。