Atcoder Beginner Contest 160 C

2020年4月12日

Atcoder Beginner Contest 160 C を Python で

Atcoder Beginner Contest 160 C を Python で解説していきたいと思います。
今週は ABC が開催されないのかなと思っていたのですが,ついさっきホームページを見ると今週の日曜日に次の ABC162 が開催されるみたいですね!
日曜日に向けて精進していきたいと思います。
最高記録更新したいなぁ...
話がそれてしまいましたが,本題に行きましょう。まずは問題文から。
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+1Ai
で出すことができます。ただし,1番目の家と N 番目の家との区間の距離を出すときは注意が必要です。
以下の図を見てください。

N番目の家と1番目の家との距離

この図から,この円一周の長さが 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)

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

他の問題も解説しているので,ぜひご覧ください。
ABC 160 A
ABC 160 B
ABC 160 C
ABC 160 D
ABC 160 E