【ABC160 C】「Traveling Salesman around Lake」を解く【Python3】

abc160c

コンテスト一覧へ

 

1周Kメートルの円形の湖に沿って移動した場合、N軒全ての家を訪ねることができる最短距離を求める問題です。

提出
k, n = map(int, input().split())
a = list(map(int, input().split()))

a.append(k+a[0])
d = 0

for i in range(n):
    d = max(d, a[i+1]-a[i])

print(k-d)

それぞれの家の間の差分を調べ、一番大きい差分の場所を歩かないように始点と終点を考えると最短距離になります。

湖の周りに沿ってのみ移動できるので、家の差分は、特定のiに対して「i番目」と「i+1番目」の間の距離を調べるだけで済みます。

N番目の家と1番目の家の距離も出すために、最初に「k+a[0]」をリストに加えています。

それぞれの家の間の距離を調べ、Kメートルから一番大きい距離を引いたものが答えになります。

スポンサーリンク

【ABC160】解説記事リスト

コンテスト一覧に戻る

コメントを残す

メールアドレスが公開されることはありません。