SRM 671 div1 med:BearDarts - mayoko’s diary

SRM 671 に参加しました。0 完太陽でレートが落ちてしまいました。med は %= MOD するとかいうしょうもないミスで落としたので辛い。

問題

解法

w[a]*w[c] = w[b]*w[d] ということは w[a]/w[b] = w[d]/w[c] ということです。ということで, 座標の最大値が i 以下のもので, w[i]/w[j] (j < i) という形の分数になるものがいくつあるのかを数えながら (a, b, c, d) の組み合わせの個数を数えていけば良いです。

得た知見

下の書き方, 普通に賢いですよね(本番は二分探索した)
- 「大小関係のある組あわせの数え上げ」で普通に応用できそうなので覚えておこう

class BearDarts {
public:
    long long count(vector <int> w) {
        int n = w.size();
        ll ans = 0;
        map<pii, int> P;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                int g = __gcd(w[i], w[j]);
                P[pii(w[i]/g, w[j]/g)]++;
            }
            for (int j = i+2; j < n; j++) {
                int g = __gcd(w[i+1], w[j]);
                ans += P[pii(w[i+1]/g, w[j]/g)];
            }
        }
        return ans;
    }
};