AtCorder|(復習)C - Average Length - 長野エンジニアライフ

昨日、完答できなかった↓の問題の復習記事です。

(準備)利用モジュールの確認

今回使用するモジュールは - permutations(順列の総数を求める) - hypot(ユークリッド距離を求める) - factorial(階乗を求める)

permutations

リスト要素の順列を生成するモジュール、順列の各要素の型はタプルとなっている、

#サンプルコード
from itertools import permutations
l = ['a', 'b', 'c']
p = permutations(l)
for elm in p:
  print(elm)

出力結果

('a', 'b', 'c')
('a', 'c', 'b')
('b', 'a', 'c')
('b', 'c', 'a')
('c', 'a', 'b')
('c', 'b', 'a')

リストlは3要素からなるため、このリストの順列の総数は3! = 6通りある。

hypot

点Pの座標を(x, y)としたとき、hypot(x, y)の値は点Pと原点からのユークリッド距離 ${\sqrt{x^2 + y^2}}$ となります。

#サンプルコード
from math import hypot
p = (3, 2)
d = hypot(p[0], p[1])
print(d)

出力結果

3.605551275463989

原点(0, 0)と点P(3, 2)のユークリッド距離は ${\sqrt{3^2 + 2^2}}$ = ${\sqrt{15}}$ = 3.6055...となる。

factorial

引数(整数)の階乗を返す関数。

#サンプルコード
from math import factorial
print(factorial(3))

出力結果

(3! = 3 * 2 * 1 = 6)

解説

以下、AC解答例

from itertools import permutations
from math import hypot, factorial
N = int(input())
a = [list(map(int, input().split())) for _ in range(N)]
 
total = 0
for p in permutations(a):
    for i in range(N-1):
        total += hypot(p[i][0]-p[i+1][0], p[i][1]-p[i+1][1])
    
print(total / factorial(N))

以下の手順で解答の値が算出できる。 1. permutations(a)で各町の座標を持った点の順列の総数を取得する 2. 1.で取得した各順列の先頭要素から末尾要素までの距離を加算する 3. 2.で加算した総和を(町の数)!で割る

最後に、復習した上で自前コードを書きます。

復習コード

from itertools import permutations
from math import hypot, factorial
n = int(input())
t = [list(map(int,input().split())) for _ in range(n)]

sum = 0
for p in permutations(t):
  for i in range(n-1):
    sum += hypot(p[i+1][0]-p[i][0], p[i+1][1]-p[i][1])
print(sum/factorial(n))

個人的に２点間の距離は(後ー前)の方がイメージしやすいので、hypotの引数は少し修正しています。

今週もお疲れ様でした。

参考記事

note.nkmk.me