読者です 読者をやめる 読者になる 読者になる

TopCoder SRM 671 Div1 Medium: BearDarts

解法


コード

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);
    }

}