kmjp's blog

競技プログラミング参加記です

Codeforces #673 Div1 B. Make Them Equal

また変な設定の問題。
https://codeforces.com/contest/1416/problem/B

問題

1-originの整数列Aが与えられる。
このAに以下の処理を繰り返す。

  • A[i]からiの倍数である正整数を引き、その分をA[j]に足す

Aを3*|A|回以下の処理で全要素等しくできるか判定せよ。

解法

まず全要素の総和が|A|の倍数であることが前提。
A[1]にすべてを集めてしまえば、そこから各要素に値をばらまくのは簡単。
そこでまずA[1]にすべて集めよう。
A[i]→A[1]に値を集めるとき、A[i]がiの倍数でない場合は、不足分をいったんA[1]から借りればよい。

int T;
int N;
int A[10101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		int sum=0;
		FOR(i,N) {
			cin>>A[i+1];
			sum+=A[i+1];
		}
		if(sum%N) {
			cout<<-1<<endl;
			continue;
		}
		sum/=N;
		vector<vector<int>> V;
		for(i=2;i<=N;i++) {
			int lef=(i-A[i]%i)%i;
			V.push_back({1,i,lef});
			A[1]-=lef;
			A[i]+=lef;
			V.push_back({i,1,A[i]/i});
			A[1]+=A[i];
			A[i]=0;
		}
		assert(A[1]==sum*N);
		for(i=2;i<=N;i++) {
			assert(A[i]==0);
			V.push_back({1,i,sum});
		}
		
		cout<<V.size()<<endl;
		FORR(v,V) cout<<v[0]<<" "<<v[1]<<" "<<v[2]<<endl;
		
		
	}
		
}

まとめ

解いたのすでに14か月以上前だしなぁ。