Codeforces #183 Div1. C. Minimum Modular

練習で解こうとしたが、Editorial見てもえらく苦戦した問題。
http://codeforces.com/contest/303/problem/C

＝＝＝＝

問題

N個の異なる整数列Aが与えられる。
ここで最大K(<=4)個の要素を取り除くことができるとき、A[i]=A[j] (mod M)となるi,jがなくなるような最小のMを答えよ。

解法

A[i]=A[j] (mod M)となるということは、差D(i,j) = |A[i]-A[j]| = p*Mということになる。
先に差Dの値毎に(i,j)のペアを全部列挙しておく。

あとはMを1から順に大きくして条件を満たせるか見ていく。
あるMが条件を満たすなら、K個点を取り除くことで差がM、2M、3M…となるようなペア群を空にできるはずである。

以下のコードでは、先にペア群を求め、登場数が多い要素を順位K個引いている。

愚直に書くとTLEするので随所で枝刈り。
vectorは使わないようにするとか、ペア数が多くて条件を満たせないならさっさと次のループに行くとか。

int N,K;
vector<int> V;
int num[5001];
int mat[5001][5001];
int nd[1000002],ne[1000002];
pair<int,int> dif[1000002][12];

void solve() {
	int f,r,i,j,k,l, x,y;
	
	cin>>N>>K;
	FOR(i,N) V.push_back(GETi());
	FOR(i,N) for(j=i+1;j<N;j++) if(nd[abs(V[j]-V[i])]<10) dif[abs(V[j]-V[i])][nd[abs(V[j]-V[i])]++] = make_pair(i,j);
	j=1000002;
	for(i=1000001;i>=1;i--) {
		ne[i]=j;
		if(nd[i]) j=i;
	}
	for(i=1;i<=1000001;i++) {
		ZERO(num);
		
		vector<int> VV;
		l=0;
		for(j=i;j<=1000000;) {
			if(nd[j] >= 8) goto eout;
			l+=nd[j];
			if(l>K*(K+1)/2) goto eout;
			if(ne[j]<=j+i) j+=i;
			else j=(ne[j]/i)*i;
		}
		
		l=0;
		for(j=i;j<=1000000;j+=i) {
			FOR(k,nd[j]) {
				mat[dif[j][k].first][dif[j][k].second] = mat[dif[j][k].second][dif[j][k].first] = i;
				if(++num[dif[j][k].first]==K+1) l++;
				if(++num[dif[j][k].second]==K+1) l++;
				if(l>K) goto eout;
			}
		}
		
		VV.reserve(N);
		FOR(j,N) if(num[j]) VV.push_back(j);
		
		FOR(j,K) {
			if(VV.empty()) break;
			k=0;
			FOR(l,VV.size()) {
				if(num[VV[l]]>num[VV[k]]) {
					k=l;
					if(num[VV[l]]>(K-j)) break;
				}
			}
			
			num[VV[k]]=0;
			vector<int> VV2;
			VV2.reserve(VV.size());
			x=0;
			FOR(l,VV.size()) {
				if(mat[VV[k]][VV[l]]==i) num[VV[l]]--;
				if(num[VV[l]]) VV2.push_back(VV[l]);
				if(num[VV[l]]>=K-j) x++;
			}
			VV=VV2;
			if(x>=K-j) goto eout;
		}
		if(VV.empty()) return (void)_P("%d\n",i);
		
		eout:
		;
	}
	return;
}

まとめ

うーん、本番解き方がわかってもTLEを回避できる気がしない。