ABC092 C Traveling Plan 累積和を取って計算量削減

ABC092 C Traveling Plan

問題概要

リンク参照

考察

  • 愚直に計算すると:O(n^2)かかるので計算量削減が必要.どう減らすか?
  • 観光スポットを削除する部分以外は毎回コストは変わらないので毎回計算するのは無駄
  • 今回は観光スポットを消さない場合のコストの総和(sumとする)を前処理で求めておいて,観光スポットiを消す場合について,sum-(観光スポットをiとi+1の間のコスト)-(観光スポットをiとi-1の間のコスト)+(観光スポットをi-1とi+1の間のコスト)を出力すれば:O(n)で間に合う

なお,バグりました

うく

ソースコード

#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<climits>

using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define ARRAY_MAX 100005
const int INF = INT32_MAX / 3;
const ll MOD = 1e9 + 7;

int dx[4] = { 1,0,0,-1 };
int dy[4] = { 0,1,-1,0 };


/******************************************************************************************/


int main() {

	int n;
	cin >> n;
	vector<int> a;
	a.push_back(0);

	ll sum = 0;

	for (int i = 0; i < n; i++)
	{
		int c;
		cin >> c;
		a.push_back(c);
	}

	a.push_back(0);

	n += 2;

	for (int i = 0; i <= n - 2; i++)
	{
		sum += abs(a[(i + 1) % n] - a[i]);
	}

	for (int i = 1; i <= n - 2; i++)
	{
		cout << sum - abs(a[(i + 1) % n] - a[i]) - abs(a[i] - a[(i + n - 1) % n]) + abs(a[(i + 1) % n] - a[(i + n - 1) % n]) << endl;
	}


	return 0;
}