タムログ

プログラミングについての情報発信をしていきます!

Atcoder Beginner Contest 160 C を Python で

Atcoder Beginner Contest 160 C を Python で解説していきたいと思います。まずは問題文から。
https://atcoder.jp/contests/abc160/tasks/abc160_c


C – Traveling Salesman around Lake


実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 300 点

問題文

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

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

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

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

制約

  • 2≤K≤106
  • 2≤N≤2×10^5
  • 0≤A1<…<AN<K
  • 入力中のすべての値は整数である。

入力

入力は以下の形式で標準入力から与えられる。

K N
A1 A2  AN

出力

いずれかの家から出発して N 軒すべての家を訪ねるための最短移動距離を出力せよ。


解説

これはいわゆる巡回セールスマン問題ですね。円形に配置された家の全てを通る最小の距離を考えるという問題になります。
家が N 個あるので,円形の湖はこの家によって N 個の区間に分かれています。
いずれかの家から出発するので,すべての家を通るとき,N 個の区間のうち通らない区間は1つだけになります。よって,最も長い区間をこの通らない区間に設定することで最短距離を求めることができます。

従って,最も長い区間を出すことを試みます。i 番目の家と i+1 番目の家の区間の距離は
Ai+1 – Ai
で出すことができます。ただし,1番目の家と N 番目の家との区間の距離を出すときは注意が必要です。この円一周の長さが K であったので,1番目の家と N 番目の家との距離は
K – (AN – A1)
で出せることが分かります。
以上より,それぞれの区間の距離は以下のように出せます。

  • Ai+1 – Ai (1≦i≦N-1)
  • K – (AN – A1)

この中から最大値を出せばいいわけです。それは最大値を longest とし,まずは longest に K – (AN – A1) を代入して,そのあと for 文でループして出すことにします。
それでは,解答例に移ります。

解答例

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

longest = k - (a[-1] - a[0])

for i in range(n-1):
    if a[i+1] - a[i] > longest:
        longest = a[i+1] - a[i]

print(k-longest)

いかがだったでしょうか。
もし分からないところがあればコメントをお願いします。
それでは!