
このシリーズではレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】でまとめられている100問をPythonで解いています。
問題
AtCoder Beginner Contest 145 C - Average Length
ポイント
この問題は順列全探索を用いて解いていきます。(Pythonではitertoolsのpermutationsを使うと便利です。)
求められているのは町を訪れる経路の移動距離平均なので、
①町を訪れる経路の全パターンを洗い出す
②それぞれのパターンの移動距離と、その総和を求める
③総和をパターンの数で割る
といった流れで解答を求めていきます。
コード
def main():
import itertools
import math
N = int(input())
towns = [list(map(int, input().split(" "))) for i in range(N)]
# ①町を訪れる経路の全パターンを求める
patterns = list(itertools.permutations(towns))
# ②それぞれのパターンの移動距離と、その総和を求める
sum_distance = 0 # 総和をここに格納
for p in patterns:
for i in range(len(p) - 1):
n = i + 1
sum_distance += math.sqrt((p[i][0] - p[n][0]) ** 2 + (p[i][1] - p[n][1]) ** 2) # 移動距離を足す
# ③総和をパターン数で割る
print(sum_distance / len(patterns))
if __name__ == '__main__':
main()