問題の解説を読んで劣等感をおぼえる

今回は工夫して全列挙すると解ける問題に挑戦してみました。
問題をざっくりと言うと、スーパーに入ってお目当ての品物2つを買うお客さんがN人（最大で30人）いて、入口と出口の位置をどこにしたら移動量が最小になるかを解く問題。

atcoder.jp

入力例と答えから、なんとなく入口と出口はN人のうちの誰かの品物の位置に合わせた方が良いと思いつきました。
入口の候補がN個、出口の候補がN個、そして入口と出口を固定した後にN人の移動距離を計算するので、計算量はざっと。
Nは最大で30なので30*30*30=27000なら全列挙できる！！全列挙して解きました。
あっさりと正解できたのですが、解説を読んで劣等感を味わった一文は次の通りです。

N個の数があった時、の最小値を求めるときに、最小値となるの値はの中央値となる。

えっ、そうなの？解説にあった感覚的な説明では理解できず色々と調べてしまいました。
結局、RPubs - 中央値を実感するの数式を使った説明で納得しました。
回帰の誤差、２乗するか絶対値をとるか - Qiitaという記事も面白くて、最小二乗法しか最近は使ってなかった私は最小絶対値法という存在と誤差の奥深さにハマり、競プロとは異なる世界で1時間ほど脱線していました。

話を問題に戻すと、移動距離は、入口から1つ目の商品の距離 + 2つの品物の距離 + 2つ目の商品から出口までの距離のN人分の合計になるので、
入口から1つ目の商品の距離は、入口の位置を、1つ目の商品の位置をとしたときに、
2つ目の商品から出口までの距離は、出口の位置を、2つ目の商品の位置をとしたときに、
となって、
結局、との中央値が移動距離が最小になる入口と出口の位置になります。
中央値はソートして、配列の要素数を2で割った切り捨て値の位置の値になります。
言葉だと伝わらなさそうなので、

org_list.sort()
median = org_list[len(org_list) // 2]

sortの計算量がなので、で求められることになります。
しか思いつかなかった。。。自力でこの頭の良い解法に気づける日は来るのだろうか。。。

N = int(input())
ab_arr = []
minimum = 1 << 64 - 1
for _ in range(N):
    a, b = list(map(int, input().split()))
    ab_arr.append((a, b))
for i in range(N):
    for j in range(N):
        iri = ab_arr[i][0]
        degu = ab_arr[j][1]
        amount = 0
        for ab in ab_arr:
            amount += abs(iri - ab[0]) + abs(ab[0] - ab[1]) + abs(ab[1] - degu)
        minimum = min(amount, minimum)
print(minimum)