【ABC過去問演習】160,159 の C 問題 - プログラミング関連の記録

はじめに

リアルタイムでコンテストに参加してみて、なかなか ABC の C 問題が解けないと感じたので練習することにした。新しい問題から古い問題にさかのぼる形で演習していく。毎回本記事のような形で記録を残すのは骨が折れそうなので、基本的には解いた問題の感想だけ書くようにしようと思う。

ABC160 C問題

問題概要

一周 $K$ メートルの池がある。池の周りには $N$ 軒の家が建っている。それぞれの家は池の適当な点から左回りに $A_N$ メートルの位置にある。適当な家から出発して $N$ 軒の家をすべて回るのに必要な最短の距離を求めよ。

制約

省略

解法

最も離れた隣り合う２つの家の距離を池の外周から引けば答えが求まる。自分は家の位置を格納した配列 A を昇順にソートしてから、A.at(i+1)-A.at(i) の最大値を調べ上げることにした。ただし A に格納されているのは左回りの経路をとった場合の起点からの距離なので、A.at(i+1)-A.at(i) が池の半周より大きくなっている場合は $K-(A.at(i+1)-A.at(i))$ が隣り合う2軒間の距離となる。

ACしたコード

#include<bits/stdc++.h>
using namespace std;
int main(){
  int k,n;cin>>k>>n;
  int tmp;
  int ans=0;
  vector<int>a(n);
  for(int i=0;i<n;i++){
    cin >>a.at(i);
  }
  sort(a.begin(),a.end());
  for(int i=0;i<n-1;i++){
    tmp=a.at(i+1)-a.at(i);
    if(tmp>k/2)
    tmp=k-tmp;
    ans=max(ans,tmp);
  }
  tmp=a.at(n-1)-a.at(0);
  if(tmp>k/2)
    tmp=k-tmp;
  ans=max(ans,tmp);
  cout <<k-ans<<endl;
}