Python3で解く AtCoder Beginner Contest 145 C - Average Length
街が個あるので全部パターン数えていると計算量が大きくなってしまう。最終的に平均の距離を出すのでそこも合わせて工夫する
概要
- 街が個あり、座標が与えられる。
- 全ての街に1回ずつ行く。そのパターンは通りである。
- すべての移動距離(直線距離)の平均は?
解くときに考えた内容
全部の経路とその距離を計算するパターン
行き方がパターンあるので、なので、40320程度の計算だから普通に全部計算すればいい。同じ場所を何回通るのかを考えて、全ての街組みわせを出して、その距離の和を計算するパターン
少し工夫して、同じ経路を何回行くのかというのを考える。同じ経路になる部分を とすると という2パターンがあって、と残りそれ以外個の行き方なので回同じ経路を辿っていることになる。なので全ての街組みわせを出して、その距離の和を とすると となる。
コード
愚直に、全経路パターンの和を出す方法
from itertools import permutations # 距離計算 def distance(x1, y1, x2, y2): return((abs(x1-x2)**2 + abs(y1-y2)**2) ** (1/2)) # 全パターン計算する時 # 愚直なやり方 n = int(input()) l = list(range(n)) # 全ての経路パターンリスト perm = list(permutations(l, n)) perm_l = len(perm) a = [0] * n b = [0] * n 街のx, yを読み込み for i in range(n): a[i], b[i] = map(int, input().split()) ans = 0 # 全ての経路パターンで for p in perm: # 経路を順に一つずつずらして距離を足して行く for i in range(n-1): ans += distance(a[p[i]], b[p[i]], a[p[i+1]], b[p[i+1]]) print(ans/perm_l)
各街同士の距離の和を出して、重複回数をかける方法
from itertools import combinations # 距離計算 def distance(x1, y1, x2, y2): return((abs(x1-x2)**2 + abs(y1-y2)**2) ** (1/2)) n = int(input()) l = list(range(n)) # 2つの街番号の組み合わせ comb = list(combinations(l, 2)) X = [0] * n Y = [0] * n # 街のx, yを読み込み for i in range(n): X[i], Y[i] = map(int, input().split()) ans = 0 # 全ての辺の組み合わせの距離の和 for i, j in comb: ans += distance(X[i], Y[i], X[j], Y[j]) # 各辺が使われる数は2(N-1)! # 全てのパターンはN! # 求める各辺の合計 * 2(N-1)! / N! print(ans*2/n)