Codeforces #156 Div1 A (256 A) Almost Arithmetical Progression

問題

a1 = p
ai+1 = ai * (-1)^i + q
（ただし、p, qは整数）を満たす数列を、ほぼ等差数列と呼ぶ。

与えられた数列b[i]の必ずしも連続しない部分列で、ほぼ等差数列になっているもののうち、最大の長さをもつものの長さを求めよ。

制約条件

n≦4000
0≦b[i]≦10^6

方針

ほぼ等差数列は、x y x y x...と、二つの値を繰り返し取る数列になる。
（x = yの場合もある）

なので、x, yの値を決めうちして、それがどれだけの長さを持てるかを調べればよい。
これは一見O(n^3)の計算量がかかるように見えるが、

• next[i][j]に、i番目の項の次に値jが出てくるのはいつかという配列を前計算しておく
• 同じ値の組に対しては、一度しか計算しない

という工夫をすればO(n^2)で計算できる。

ソースコード

int n, a[4000];
int next[4010][4000];

int main(){
	vi vs;
	cin >> n;
	rep(i, n) cin >> a[i], vs.pb(a[i]);
	sort(all(vs));
	vs.erase(unique(all(vs)), vs.end());
	
	memset(next, -1, sizeof(next));
	for(int i = n - 1; i >= 0; i--) rep(j, vs.size()){
		next[i][j] = next[i + 1][j];
		if(a[i] == vs[j]) next[i][j] = i;
	}
	
	int ans = 1;
	rep(q, vs.size()){
		vi v;
		rep(i, n) if(a[i] == vs[q]) v.pb(i);
		rep(r, vs.size()){
			int cnt = 1;
			int cur = v[0] + 1;
			while(cur < n){
				cur = next[cur][r];
				
				if(cur < 0) break;
				cnt++;
				cur++;
				
				if(cur >= n) break;
				cur = next[cur][q];
				
				if(cur < 0) break;
				cnt++;
				cur++;
			}
			ans = max(ans, cnt);
		}
	}
	cout << ans << endl;
	return 0;
}