Codeforces ECR #014 : F. Couple Cover

これはしっかり解けて良かったね。
http://codeforces.com/contest/691/problem/F

問題

N要素の数列Aが与えられる。ここから異なる2つのindexの対(i,j)を選び、面積A[i]*A[j]の長方形を作ることを考える。

ここでM個のクエリが与えられる。
各クエリPに対し、A[i]*A[j]≧Pとなる(i,j)の組み合わせを求めよ。

解法

Nは大きいので(i,j)を列挙することはできない。
ただPの上限が小さいことので、1～max(P)の範囲の長方形の数を列挙してしまおう。
B[x] := (A[i]=x)であるようなiの個数
S[a] := 面積S[a]である長方形の個数
とする。

各xに対し、x*y≦max(P)の範囲で総当たりし、S[x*y] += B[x]*B[y] (ただしx==yの時だけは同じindexの二重カウントを防ぐためB[x]*(B[x]-1))でS[a]を数え上げる。
また、A[i]*A[j]がmax(P)を超えるケースがあるが、それはindexの対の選び方N*(N-1)からsum(S[1..max(P)])を引けばよい。

あとはクエリPに対し、a≧Pにおけるsum(S[a])を答えよう。
これは前処理で累積和を取っておけば1クエリO(1)で処理できる。

int N,M;
ll A[3010101];
ll tot[3030303];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d",&N);
	FOR(i,N) scanf("%d",&x), A[x]++;
	
	ll tt=1LL*N*(N-1);
	for(i=1;i<=3000000;i++) {
		for(j=1;i*j<=3000000;j++) {
			if(i==j) tot[i*j] += A[i]*(A[i]-1), tt -= A[i]*(A[i]-1);
			else tot[i*j] += A[i]*A[j], tt -= A[i]*A[j];
		}
	}
	tot[3000001] = tt;
	for(i=3000000;i>=0;i--) tot[i] += tot[i+1];

	
	scanf("%d",&M);
	FOR(i,M) {
		scanf("%d",&x);
		_P("%I64d\n",tot[x]);
	}
	
}

まとめ

このぐらいの問題だと実装が楽なので、教育感ありそう？