TopCoder SRM 671 Div1 Medium: BearDarts

解法

Med、a/b=c/dという変形は考えたのにそれを使って単に舐めるだけでシンプルに解く方法に至らなかったのは酷い･･･それにしてもみんな早く解きすぎじゃないですかね

— ＳＫＹ/sky58 (@skyaozora) 2015, 10月 14

コード

import java.util.HashMap;

public class BearDarts {

    public long count(int[] w) {
	int N = w.length;
	HashMap<String, Long> map = new HashMap<>();
	for (int a = 0; a < N; a++) {
	    for (int b = a + 1; b < N; b++) {
		int A = w[a];
		int B = w[b];
		int g = gcd(A, B);
		A /= g;
		B /= g;
		String keyString = A + "/" + B;
		if (map.containsKey(keyString)) {
		    map.put(keyString, map.get(keyString) + 1);
		} else {
		    map.put(keyString, 1L);
		}
	    }
	}

	long ans = 0;
	for (int mid = 0; mid < N; mid++) {
	    for (int high = mid + 1; high < N; high++) {
		int A = w[mid];
		int B = w[high];
		int g = gcd(A, B);
		A /= g;
		B /= g;
		String keyString = A + "/" + B;
		if (map.containsKey(keyString)) {
		    map.put(keyString, map.get(keyString) - 1);
		}
	    }
	    for (int low = 0; low < mid; low++) {
		int C = w[mid];
		int D = w[low];
		int g = gcd(C, D);
		C /= g;
		D /= g;
		String keyString = C + "/" + D;
		if (map.containsKey(keyString)) {
		    ans += map.get(keyString);
		}
	    }
	}
	return ans;
    }

    private int gcd(int a, int b) {
	if (b == 0) {
	    return a;
	}
	return gcd(b, a % b);
    }

}