TopCoder SRM 640 Div2 Hard TwoNumberGroupsEasy

これは自力で解けた。
http://community.topcoder.com/stat?c=problem_statement&pm=13552

問題

２つの整数集合S,Tを考える。
共に同一要素を複数持っていても良い。
2つの集合の差分とは、両者の内容が同じになるまで両集合から削除しなければいけない要素数の最小値を示す。

Sには整数A[i]がnumA[i]個ずつ、Tには整数B[i]がnumB[i]個ずつ含まれる。
ここで、整数Mに対しS%MとはSの各要素xをx%Mで置き換えたものとする。

Mに２以上の任意の整数を用いることができるとき、(S%M)と(T%M)の差分を最小化せよ。

解法

Mが定まれば、(S%M)と(T%M)の差分は容易に定まる。
よってあとはMの候補をどう絞り込むかが問題となる。

Mとして|A[i]-B[j]|の約数を取ると、A[i]%MとB[j]%Mが一致するので少なくともmin(numA[i],numB[j])だけ差分が縮むことが期待できる。
よってそのようなMを総当たりすると良い。

以下の候補では念のため|A[i]-A[j]|など他の候補も試している。

class TwoNumberGroupsEasy {
	public:
	vector <int> A,numA,B,numB;
	int dist2(int M) {
		map<int,ll> m1,m2;
		int i,j;
		int ret=0;
		FOR(i,A.size()) m1[A[i]%M] += numA[i], ret+=numA[i];
		FOR(i,B.size()) m2[B[i]%M] += numB[i], ret+=numB[i];
		ITR(it,m1) ret-=2*min(it->second,m2[it->first]);
		return ret;
	}
	
	int dist(int M) {
		if(M<=1) return 1<<30;
		int i;
		int ret=dist2(M);
		for(i=2;i*i<=M;i++) if(M%i==0) {
			ret=min(ret,dist2(i));
			ret=min(ret,dist2(M/i));
		}
		return ret;
	}
	
	int solve(vector <int> A_, vector <int> numA_, vector <int> B_, vector <int> numB_) {
		A=A_; B=B_; numA=numA_; numB=numB_;
		int ret=dist(1<<30),x,y;
		FOR(x,A.size()) if(A[x]>1) ret=min(ret,dist(A[x]));
		FOR(x,B.size()) if(B[x]>1) ret=min(ret,dist(B[x]));
		FOR(x,A.size()) FOR(y,A.size()) ret=min(ret,dist(abs(A[x]-A[y])));
		FOR(x,A.size()) FOR(y,B.size()) ret=min(ret,dist(abs(A[x]-B[y])));
		FOR(x,A.size()) FOR(y,A.size()) ret=min(ret,dist(abs(B[x]-B[y])));
		
		return ret;
	}
}

まとめ

割とあてずっぽうでMの候補を求めたけど正解で良かった。