AtCoderログ：0095 - ABC 160 C

問題

問題文

$1$ 周 $K$ メートルの円形の湖があり、その周りに $N$ 軒の家があります。
$i$ 番目の家は、湖の北端から時計回りに $A_i$ メートルの位置にあります。
家の間の移動は、湖の周りに沿ってのみ行えます。
いずれかの家から出発して $N$ 軒すべての家を訪ねるための最短移動距離を求めてください。

制約

・$2 \le K \le 10^6$
・$2 \le N \le 2×10^5$
・$0 \le A_1 < \ldots < A_N < K%
・入力中のすべての値は整数である。

収録されている問題セット

• [BfB-E](AtCoder Problems Boot camp for beginners Easy 100) #012

回答

回答1 (AC)

$i-1$ 番目の家と $i$ 番目の家の距離は $A_i-A_{i-1}$ なので、$i$ 番目の家を出発して時計回りにそれぞれの家を訪ね、最後に $i-1$ 番目の家を訪ねるときの移動距離は $K-(A_i-A_{i-1})$ となります。後は $i$ を変化させたときの最小値を求めれば良いでしょう。ただし $i \ge 2$ でなければならないので、$i=1$ の場合は別扱いが必要なことに注意してください。コードは以下のようになりました。

abc160c-1.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
  int k, n;
  cin >> k >> n;

  vector<int> a(n);
  for ( int i=0; i<n; i++ ) {
    cin >> a.at(i);
  }
  
  int dmin = a.at(n-1)-a.at(0);
  for ( int i=1; i<n; i++ ) {
    dmin = min( dmin, k-(a.at(i)-a.at(i-1)) );
  }
  
  cout << dmin << endl;
}

調べたこと

AtCoder の解説 → ユーザ解説

回答1と同じ方針でした。

AtCoder の解説 → コンテスト全体の解説

回答1と同じ方針でした。

リンク

前後の記事

• 前の記事 → AtCoderログ：0094 - ABC 074 B
• 次の記事 → AtCoderログ：0096 - AGC 014 A