ABC160の復習

初めに

ABC160に参加した時の復習です。その時はC問題が解けずに終わってしまい、
解説を見て解き直しましたが、今まで使ったことが無い考え方が必要な問題だったので
忘れないように復習しようと思います。

https://atcoder.jp/contests/abc160

※ブログ内で問題の制約事項をすべて記載はしないので、制約事項は↑のURLより参照願います。

C - Traveling Salesman around Lake

1周Kメートルの湖がありその周りにN軒の家があります。それぞれの家はAiメートル離れていて、 湖に沿ってN軒すべての家に訪問する際の最短距離を求める問題です。

#include<bits/stdc++.h>

using namespace std;
const long long INF = 1LL<<60;

int main(){

long long K,N;
long long ans = INF;
long long total = 0;

cin >> K >> N;

vector<long long> A(N);

for(long long i = 0; i < N; ++i) cin >> A[i];

// 
A.push_back(A[0]+K);

long long l = 0;

for(long long i = 0; i < A.size(); ++i){

 // それぞれの家と家との間の距離の最大値を求める
    l = max(l,A[i+1] - A[i]);

}

// 一周の長さから家間の距離の最大値を削除する。
cout << K - l << endl;

return 0;

}   

これは円環の問題と言われるらしく、下記イメージのように輪っか上の何かを扱う問題です。

f:id:hgm_blog:20200531165453j:plain
イメージ

グラフで表すと以下イメージのようになります。
この問題は一直線ですべての家に回る経路が最短になるため、
各家への道のうち最も長い道を削除すると最短経路が求まります。
(一度通った点を折り返すパターンでは無い)

f:id:hgm_blog:20200531170937j:plain
イメージ

上記のイメージは解いている途中に何となく浮かんだんですが、
0を跨ぐパターンをどうやって計算するかが思い浮かびませんでした。
解説を見たところ円環の問題でよく使わるやり方としては
上記のグラフを切り開いて0を跨ぐ場合はK+A1の形で表す事で
それぞれの家との距離を求める事が可能になります。
(以下のように切り開いていて2周分の距離の中で計算を行う。)

f:id:hgm_blog:20200531174133j:plain
イメージ

あと、それぞれの家との距離の最大値を求めてKから引けば答えが求まります。

最後に

この記事を書いていて感じたが、やっぱり時間が立つと結構抜けてしまいますね。
ずっと覚えている事は難しいのでこのような形ですぐに思い出せるように残しておきたいですね。