Code Formula 2014 本選 : H - 平和協定

これもまぁまぁあっさり。
http://code-formula-2014-final.contest.atcoder.jp/tasks/code_formula_2014_final_h

問題

N個の国はパラメータとしてA[i]、B[i]の２値を持つ。
２つの国p,qは、S1 ≦ (A[p]-A[q])*(B[p]-B[q]) ≦ S2なら仲良くできる。
仲良くできる国の対の数を答えよ。

解法

各国pに対し、A[p]＜A[q]かつB[p]＜B[q]で、かつ(A[q]-A[p])*(B[q]-B[p]) ≦ S2となるqの数を数えたのち、(A[q]-A[p])*(B[q]-B[p]) ≦ S1-1となるqの数を引けばよい。

ここで、(A[q]-A[p])*(B[q]-B[p]) ≦ Dとなるqの数の高速な数え方を考える。
この場合、(A[q]-A[p])と(B[p]-B[q])のどちらかは√D以下である。

よって、各A[i]=xに対応したB[i]の値を格納した配列と、B[i]=yに対応したA[i]の値を格納した配列を持っておく。

例えば、A[q]-A[p]=dxとすると、(B[q]-B[p])がD/dx以下ならそのqは条件を満たす。
この処理はupper_boundを使い、そのようなqの数は高速に求められる。

よって、以下の和を足せばよい。

• (x-A[p])≦√Dとなる範囲のxで、A[q]==xかつ(B[q]-B[p])<=D/xとなる数を求める。
• (y-B[p])≦√Dとなる範囲のyで、B[q]==yかつ√D ＜ (A[q]-A[p])<=D/xとなる数を求める。

２つ目の式で√D＜の条件を付けたのは、(A[q]-A[p])≦√Dかつ(B[q]-B[p])≦√Dとなるqを二重カウントしないよう、２つ目の式では(A[q]-A[p])＞√Dだけカウントするようにしている。

計算量はO(N*√S2*logN)かな。

int N,S1,S2;
int A[50001],B[50001];
vector<int> AL[50001],BL[50001];

int dodo(int cx,int cy,int d) {
	int sq=sqrt(d)+1;
	int res=0;
	int x,y;
	for(x=1;x<=sq&&cx+x<=50000;x++) if(AL[cx+x].size() && d/x>0)
		res+=upper_bound(ALL(AL[cx+x]),cy+d/x)-upper_bound(ALL(AL[cx+x]),cy);
	for(y=1;y<=sq&&cy+y<=50000;y++) if(cx+d/y>cx+sq && BL[cy+y].size())
		res+=upper_bound(ALL(BL[cy+y]),cx+d/y)-upper_bound(ALL(BL[cy+y]),cx+sq);
	return res;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>N>>S1>>S2;
	FOR(i,N) {
		cin>>A[i]>>B[i];
		AL[A[i]].push_back(B[i]);
		BL[B[i]].push_back(A[i]);
	}
	FOR(i,50001) sort(ALL(AL[i])),sort(ALL(BL[i]));
	
	ll ret=0;
	FOR(x,N) ret+=dodo(A[x],B[x],S2)-dodo(A[x],B[x],S1-1);
	cout << ret << endl;
}

まとめ

やはりCode Formulaは速度重視なのか、難易度は高くないけど分量は多かったね。