くろたんく雑記帳

日常とか、わんちゃんとか、機械学習とか、競プロとか、

MENU
トップ > AtCoder > Python3で解く AtCoder Beginner Contest 145 C - Average Length

Python3で解く AtCoder Beginner Contest 145 C - Average Length

AtCoder 競プロ ABC-C 直線距離 組み合わせ 重複

街が{\displaystyle N}個あるので全部パターン数えていると計算量が大きくなってしまう。最終的に平均の距離を出すのでそこも合わせて工夫する

概要

問題

  1. 街が{\displaystyle N}個あり、座標が与えられる。
  2. 全ての街に1回ずつ行く。そのパターンは{\displaystyle N!}通りである。
  3. すべての移動距離（直線距離）の平均は？

解くときに考えた内容

  • 全部の経路とその距離を計算するパターン
    行き方が{\displaystyle N!}パターンあるので、{\displaystyle 2 \leqq N \leqq 8}なので、40320程度の計算だから普通に全部計算すればいい。

  • 同じ場所を何回通るのかを考えて、全ての街組みわせを出して、その距離の和を計算するパターン
    少し工夫して、同じ経路を何回行くのかというのを考える。同じ経路になる部分を{\displaystyle a, b} とすると {\displaystyle ab, ba}という2パターンがあって、{\displaystyle ab}と残りそれ以外{\displaystyle N-2}個の行き方なので{\displaystyle 2 \times (N-1)!}回同じ経路を辿っていることになる。なので全ての街組みわせを出して、その距離の和を {\displaystyle L}とすると {\displaystyle L\times \frac {2 \times (N - 1)!}{N!} = L\times \frac {2}{N} } となる。

コード

愚直に、全経路パターンの和を出す方法
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)