Edit

【pythonでABC160を解説】C - Traveling Salesman around Lake

問題概要

問題ページ

C - Traveling Salesman around Lake
C - Traveling Salesman around Lake

問題ページへ移動する

問題文

\(1\) 周 \(K\) メートルの円形の湖があり、その周りに \(N\) 軒の家があります。

\(i\) 番目の家は、湖の北端から時計回りに \(A_i\) メートルの位置にあります。

家の間の移動は、湖の周りに沿ってのみ行えます。

いずれかの家から出発して \(N\) 軒すべての家を訪ねるための最短移動距離を求めてください。

制約

  • \(2 \leq K \leq 10^6\)
  • \(2 \leq N \leq 2 \times 10^5\)
  • \(0 \leq A_1 < ... < A_N < K\)
  • 入力中のすべての値は整数である。

問題の考察

ACコード

import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    k, n = list(map(int, input().rstrip('\n').split()))
    a = list(map(int, input().rstrip('\n').split()))
    mn = k - (k - a[-1] + a[0])
    for i in range(1, n):
        mn = min(mn, k - a[i] + a[i - 1])
    print(mn)


if __name__ == '__main__':
    solve()

-Edit