Codeforces #209 Div2. D. Pair of Numbers

なんかtagやeditorialに2分探索とか書いてあるけど、二分探索は使ってないなあ。
http://codeforces.com/contest/359/problem/D

問題

数列A[i]が与えられる。以下の条件を満たす(L,R)のペアをあるだけ求めよ。

• あるj(L<=j<=R)について、A[L]～A[R]はいずれもA[j]で割り切れる。
• R-Lの値が最大である。

解法

Editorialとは違う解法で解いた。
数列の各要素A[j]について、A[j-1]、A[j-2]…と減少方向に何個A[j]で割り切れる要素が続くかを求め、同様に増加方向にA[j+1]、A[j+2]…もA[j]で割り切れる要素数を求める。
この個数より、jに対応するL,Rの値が求められる。

後は各jについてR-Lが同着で最大となるものを列挙すればよい。
これらは尺取法の要領でO(N)で処理できる。

int N;
int A[400001];
int L[400001],R[400001];
set<int> S[400001];

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	for(x=0,i=1;i<N;i++) {
		if(A[i]%A[x]) x=i;
		else L[x]++;
	}
	for(x=0,i=1;i<N;i++) {
		if(A[i]==A[x]) L[i]=L[x]-(i-x);
		if(A[i]%A[x]) x=i;
	}
	
	for(x=N-1,i=N-2;i>=0;i--) {
		if(A[i]%A[x]) x=i;
		else R[x]++;
	}
	for(x=N-1,i=N-2;i>=0;i--) {
		if(A[i]==A[x]) R[i]=R[x]-(x-i);
		if(A[i]%A[x]) x=i;
	}
	
	FOR(i,N) S[L[i]+R[i]].insert(i-R[i]);
	
	for(i=N;i>=0;i--) {
		if(S[i].empty()) continue;
		_P("%d %d\n",S[i].size(),i);
		ITR(it,S[i]) _P("%d ",*it+1);
		_P("\n");
		return;
	}
}

まとめ

同じ値が続く場合の尺取法のバグとりで少し手間取った。