【ABC145 C】「Average Length」を解く【Python3】

座標平面上に、座標(x_i, y_i)に位置しているN個の町があり、これらの町をすべて1回ずつ訪れるときの経路の長さの平均値を計算する問題です。

特定の2つの町の距離を計算し、それらをすべて足し合わせることで求めることができます。

提出

import math
n = int(input())
l = 0

xi = []
yi = []

for i in range(n):
    x, y = map(int, input().split())
    xi.append(x)
    yi.append(y)

for j in range(n):
    for k in range(n):
        if j >= k:
            continue
        l += math.sqrt((xi[j] - xi[k]) ** 2 + (yi[j] - yi[k]) ** 2)

print(l * 2/n)

for文を用いて、2つの町の距離をすべて計算し、足し合わせておきます。

町を訪れる経路は、全部でN!通りあり、その中で「特定の2つの町の距離」は同じ回数だけ使用します。

入力例1に関していうと、「町1と町2の間の距離」は4回使用されています。

「町1と町3の間の距離」、「町2と町3の間の距離」も同様です。

この回数は、2×(N-1)! で求めることができます。

（「1→2」は、N!通りの経路の中で(N-1)!回使われるので、「2→1」も考慮して、その2倍ということです）

最終的に経路の長さの平均値は、「(特定の2つの町の距離の合計) × (2×(N-1)!) / N!」となります。

さらに簡易的に、

(特定の2つの町の距離の合計)×(2/N)

で求められます。