TopCoder SRM 671 Div1 Medium: BearDarts
解法
Med、a/b=c/dという変形は考えたのにそれを使って単に舐めるだけでシンプルに解く方法に至らなかったのは酷い・・・それにしてもみんな早く解きすぎじゃないですかね
— SKY/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); } }