Codeforces #808 : Div1 B. Difference Array

AよりBの方が簡単だったかも。
https://codeforces.com/contest/1707/problem/B

問題

昇順である整数列Aが与えられる。
Aの階差数列を取り、昇順にソートしたものをAに上書きする、という処理を|A|=1になるまで繰り返す。
最終的な値は何になるか。

解法

すぐに同じ値がたくさん出てくる。
そのため、Aを愚直に持つのではなく、RLEした形で持つと、急速にAのユニークな要素数が減少する。

int T;
int N,A[303030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		
		map<int,int> M;
		FOR(i,N) {
			cin>>x;
			M[x]++;
		}
		
		
		while(M.size()>1) {
			map<int,int> W;
			int prev=-1;
			FORR2(a,b,M) {
				if(b>1) W[0]+=b-1;
				if(prev>-1) W[a-prev]++;
				prev=a;
			}
			M=W;
		}
		
		if(M.begin()->second>1) {
			cout<<0<<endl;
		}
		else {
			cout<<M.begin()->first<<endl;
		}
		
	}
}

まとめ

750ptのBは簡単目なことが多い気がする。