AGC010 B問題 Boxes

B: Boxes - AtCoder Grand Contest 010 | AtCoder

コンテスト中前半はほぼ諦めながら考えてました。

解き方を考えている内に、
最後にすべて0になる前は間違いなく
1,2,3,4,5,・・・n-1,nの順番がどこかしらかスタートで出来ることに気づく。

スタート地点からゴール地点へどのように行くか考えた時、
適当に実際に行動した場合、i地点とi+1地点の差の変化が選んだ場所によって
変わることが判明。

後は頑張ってとこうとしたが解けなかったため、
解説を見て実装。

#include <iostream>

using namespace std;

#define DEBUG 0

int main(){

	long long int n;
	long long int *a;
	long long int sum=0;
	cin>>n;
	a = new long long int[n];

	for(int i=0;i<n;i++){
		cin>>a[i];
		sum += a[i];
	}

	long long int once = n*(n+1)/2;

	if(sum%once!=0){
		if(DEBUG)cout<<"0"<<endl;
		cout<<"NO"<<endl;
		return 0;
	}
	long long int cnt = sum/once;

	if(DEBUG)cout<<"cnt="<<cnt<<endl;

	long long int *d;
	d = new long long int[n];
	for(int i=1;i<=n;i++){
		d[i-1] = a[i%n] -a[i-1] -cnt;
	}

	long long int ansCnt=0;
	for(int i=0;i<n;i++){
		while(d[i]<0){
			d[i]+=n;
			ansCnt++;
		}
		if(DEBUG)cout<<"i="<<i<<" d[i]="<<d[i]<<endl;
		if(d[i]!=0){
			if(DEBUG)cout<<"1"<<endl;
			cout<<"NO"<<endl;
			return 0;
		}
	}

	if(ansCnt==cnt){
		cout<<"YES"<<endl;
	}else{
		if(DEBUG)cout<<"2"<<endl;
		cout<<"NO"<<endl;
	}


	return 0;

}