Codeforces #736 Div1 : B. Integers Have Friends

良くもなく悪くもない回。
https://codeforces.com/contest/1548/problem/B

問題

整数列が与えられる。
その連続な部分列のうち、ある整数2以上の整数mで割った剰余が一致するようなものの最大要素数を求めよ。

解法

Aの階差数列をBとする。
GCD(B[L],B[L+1],...,B[R])＞1である[L,R]のうちR-L+1の最大値が解となる。

f(n,m) := B[f(n,m)]...B[n]のGCDがmとなるような最小のindex
とし、
f(n+1,gcd(m,B[n+1])) = min(f(n+1,gcd(m,B[n+1])), f(n,m))
で更新していこう。
考慮すべきmはさほど多くない。

m＞1におけるn-f(n,m)+1の最大値が解となる。

int T;
int N;
ll A[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) cin>>A[i];
		for(i=N-1;i>0;i--) {
			A[i]=abs(A[i]-A[i-1]);
		}
		int ret=1;
		map<ll,int> M;
		M[0]=0;
		for(i=1;i<N;i++) {
			map<ll,int> M2;
			M2[0]=i;
			FORR2(a,b,M) {
				ll v=__gcd(a,A[i]);
				if(v>1) {
					ret=max(ret,i-b+1);
					if(M2.count(v)) {
						M2[v]=min(M2[v],b);
					}
					else {
						M2[v]=b;
					}
				}
			}
			swap(M,M2);
		}
		
		cout<<ret<<endl;
		
		
	}
}

まとめ

まぁこれは典型かな。