TopCoder SRM 772 : Div1 Medium MaxPoints

これTLで先に解法見ちゃったから解けたけど、本番時間内に解けたかなぁ。
https://community.topcoder.com/stat?c=problem_statement&pm=15761

問題

2次元座標上にN個の頂点がある。
このうちの部分集合をSとする。
S内の頂点対のマンハッタン距離の総和をInside(S)、S外の頂点対のマンハッタン距離の総和をOutside(S)とする。
定数Kが与えられるので、Inside(S)-Outside(S)≦KであるようなSの最大要素数を求めよ。

解法

S外の点vをS内に入れると、S内の頂点とvの間の距離の総和分Inside(S)が増え、S外の頂点とvの間の距離の総和分Outside(S)が減る。
結局Inside(S)-Outside(S)は、Sの内容に限らずvとv以外の全頂点間の距離の総和分増える。

なので、全頂点に対し、他の頂点とのマンハッタン距離の総和を求めよう。
それが小さい順にSに追加していけばよい。

ll A[202020];
ll B[202020];
ll D[202020];
ll P[202020];
template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<ll,22> XS,YS,XN,YN;

class MaxPoints {
	public:
	int findMaxPoints(int N, vector <int> X, vector <int> Y, long long K, int seedX, int seedY) {
		A[0]=seedX;
		B[0]=seedY;
		int i;
		for(i=1;i<N;i++) A[i]=(A[i-1]*1103515245 + 12345) % 2147483648;
		for(i=1;i<N;i++) B[i]=(B[i-1]*1103515245 + 12345) % 2147483648;
		for(i=X.size();i<N;i++) X.push_back(A[i]%2000001-1000000);
		for(i=Y.size();i<N;i++) Y.push_back(B[i]%2000001-1000000);
		ZERO(XS.bit);
		ZERO(YS.bit);
		ZERO(XN.bit);
		ZERO(YN.bit);
		FOR(i,N) {
			X[i]+=1000005;
			Y[i]+=1000005;
			XS.add(X[i],X[i]);
			YS.add(Y[i],Y[i]);
			XN.add(X[i],1);
			YN.add(Y[i],1);
		}
		ll diff=0;
		FOR(i,N) {
			D[i]=0;
			D[i]+=(XS(1<<21)-XS(X[i]))-(XN(1<<21)-XN(X[i]))*X[i];
			D[i]+=(XN(X[i]-1)*X[i])-XS(X[i]-1);
			D[i]+=(YS(1<<21)-YS(Y[i]))-(YN(1<<21)-YN(Y[i]))*Y[i];
			D[i]+=(YN(Y[i]-1)*Y[i])-YS(Y[i]-1);
			diff-=D[i];
		}
		diff/=2;
		if(diff>K) return -1;
		
		sort(D,D+N);
		int ret=0;
		while(ret<N) {
			if(diff+D[ret]<=K) {
				diff+=D[ret];
				ret++;
			}
			else break;
		}
		return ret;
	}
}

まとめ

500ptとしては適度に考察のある問題。
実装は典型ではあるけど250ptにしては重いしバランスいいのかな。