ARC093 C : Traveling Plan(300)
作成日：2018.08.18
最終更新日：2018.08.18
問題概要
座標$0$から座標$A_1 , A_2 , ... , A_N$を順に経由し座標$0$へ戻る経路がある。
すべての中継地点$A_i$それぞれにおいて、そこだけを訪れない場合の最短移動距離を求めよ。
制約
$2 \leq N \leq 10^5$
$-5000 \leq A_i \leq 5000$
考え方
以下では$A_0 = A_{N+1} = 0$とする。
$A_i$を経由する時と経由しない時の差は、$A_{i-1}$$\rightarrow$$A_i$$\rightarrow$$A_{i+1}$か$A_{i-1}$$\rightarrow$$A_{i+1}$かの差のみである。
すなわち$A_i$を訪れない時の最短移動距離は、すべての中継地点を訪れる時と比べると$|A_{i+1} - A_{i-1}|-$$|A_i - A_{i-1}|-$$|A_{i+1} - A_i|$だけ変わる。
また、すべての中継地点を訪れる時の最短移動距離は$\sum_{0 \leq i \leq N}{|A_{i+1} - A_i|}$である。
よってこれを$O(N)$の前処理で求めておけば、各中継地点につき$O(1)$で答えを求めることができる。
ソースコード
マクロ等はこちら
int A[100010];
int N,S;
int main(){
cin >> N;
repp(i,0,N){
cin >> A[i+1];
S += abs(A[i+1] - A[i]);
}
S += abs(A[N]);
repp(i,1,N+1) cout << S + abs(A[i+1] - A[i-1]) - abs(A[i] - A[i-1]) - abs(A[i+1] - A[i]) << endl;
return 0;
}解法まとめ
すべての中継地点を訪れる時の最短移動距離$S=$$\sum_{0 \leq i \leq N}{|A_{i+1} - A_i|}$を求める。(8,10行)
各中継地点についての答えは、$S$に$|A_{i+1} - A_{i-1}|-$$|A_i - A_{i-1}|-$$|A_{i+1} - A_i|$を足したものである。(11行)