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行)

ARC093の他の問題 D E F

広告

自己紹介

赤になりたい競技プログラマー/バランス重視
詳しくはこちら
twitter

プライバシーポリシー

個人情報利用についてはこちら

お問い合わせ

このページに関するお問い合わせはこちら

競技プログラミングMENU

問題を解くまでの道のり

その他

全体MENU

広告