TopCoder SRM 671 Div1 Medium BearDarts

本番長々としたコードを書いたが、他の解法を見たらもっとシンプルに書いてあった。
http://community.topcoder.com/stat?c=problem_statement&pm=13951

問題

N要素の数列wが与えられる。
0≦a＜b＜c＜d≦(N-1)で、かつw[a]*w[c]=w[b]*w[d]となる(a,b,c,d)は何通りあるか。

解法

a,bを総当たりで探すとする。
w[b]/w[a] = w[c]/w[d]なので、mapでb以降のc,dにおけるw[c]/w[d]の登場回数を覚えておけばそれを足しこんでいくだけ。
分数は有理数クラスを持っていればそれを使っても良いし、なければ約分して分子と分母のペアで持っても良い。
double型で持つと精度が足りないので注意。

以下のようにしていくと、ループがO(N^2)回、mapの処理にO(log(N^2))=O(logN)、合わせて計算量がO(N^2*logN)程度で処理できる。
(厳密には約分のために互除法分がさらにかかるかも。)

bを大きい順に総当たりしていく。
その際、まずaを0～(b-1)の順で総当たりし、上記のとおりw[b]/w[a]の登場回数をmapを参照してカウントする。
bを大きい順に処理するということはbをデクリメントするわけだが、以後のデクリメント前のbは以後の処理でcとして登場する可能性がある。
よってbをデクリメントする前に、dを(b+1)～(N-1)で総当たりし、w[b]/w[d]を求めてmapの値を追加していくと良い。

色々書いたがコードはだいぶ簡単。有理数クラスを別途持っているなら数行で書ける。

class BearDarts {
	public:
	long long count(vector <int> w) {
		int N=w.size();
		map<pair<int,int>,int> M;
		
		ll ret=0;
		for(int b=N-1;b>=0;b--) {
			for(int a=0;a<b;a++) {
				int g=__gcd(w[a],w[b]);
				ret += M[{w[a]/g,w[b]/g}];
			}
			for(int d=b+1;d<N;d++) {
				int g=__gcd(w[b],w[d]);
				M[{w[d]/g,w[b]/g}]++;
			}
		}
		return ret;
	}
}

まとめ

こりゃ450pt以上の回答が出るわけだわ。
それにしても何がダーツかよくわからん。