Topcoder SRM671 Div1 Med: BearDurts

SRM671に参加。今回も0完で1321→1281(-32)。

問題

長さN(4 <= N <= 1000)の非負整数からなる数列wを渡される。a=w[i], b=w[j], c=w[k], d=w[l] (i < j < k < l)としたとき、ac = bd となるような選び方は何通りあるか答えよ。

解法

式を変形して a/b = d/c を考える。どこまでをa, bの候補として使うかのループiを回していき、ある既約分数となる値の組み合わせを数え上げていく。各iでc=w[i+1]、d=w[j] (j > i+1)を取り、その既約分数となるa,bの組み合わせがいくつあるかを足しあわせていけば答えとなる。

class BearDarts {
public:
  int gcd(int a, int b) {
    while (b) swap(a %= b, b);
    return a;
  } 

  ll count(vector<int> w) {
    int n = w.size();
    map<pair<int, int>, int> s;
    ll ans = 0;
    for (int i = 1; i < n; i++) {
      for (int j = 0; j < i; j++) {
        int g = gcd(w[i], w[j]);
        s[make_pair(w[j]/g, w[i]/g)]++;
      }
      for (int j = i + 2; j < n; j++) {
        int g = gcd(w[i + 1], w[j]);
        ans += s[make_pair(w[j]/g, w[i + 1]/g)];
      }
    }
    return ans;
  }
};