競プロ初中級者100問

ABC145C Average Length

この記事で使うアルゴリズム

全探索

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

https://atcoder.jp/contests/abc145/tasks/abc145_c

この問題は全探索を用いて解くことができます。

コード

Nが十分に小さいので全探索しても間に合います。その場合、計算量はO(N!N)です。

しかし、さらに計算量を減らす方法を考えます。各経路の距離の期待値について考えます。すると

各経路の距離の期待値 = 各町の間の距離の期待値 * (N-1)

となることが分かります。つまり、各町の間の距離を計算すればよく、これは計算量O(N^2)です。

1
2
3
4
5
6
7
8
9
10
11
from itertools import combinations
N = int(input())
town = []
for n in range(N):
    x, y = map(int,input().split())
    town.append((x,y))

ans = 0
for i,j in combinations(town,2):
    ans += ((i[0]-j[0])**2 + (i[1]-j[1])**2)**0.5
print (2*ans/N)

記事情報

  • 投稿日：2020年5月9日
  • 最終更新日：2020年5月9日