[Codeforces] Codeforces Round #672 (Div. 2) B. Rock and Lever

2020年9月25日2020年12月12日

問題

方針

自然数 \( a, b \) が

\[ a \ \& \ b \geq a \oplus b\]

を満たすとき、\( 2^{i} \leq a, b \leq 2^{i+1} -1 \) を満たす \( i \) が存在します。これは同じビット数で表現できる数は、最高位のビットがともに \( 1 \) なので、\( a \oplus b \) の最高位のビットは \( 0 \) となるからです。一方で、異なるビット数の論理積は最高位のビットが \( 0 \) となり、排他的論理の最高位のビットは \( 1 \) となります。

したがって、\( 2^i \leq a_j \leq 2^{i + 1} – 1\) となる \( a_j \) の数を \( m \) とすると、

\[ \dfrac{m(m-1)}{2}\]

個のペアが存在ます。与えられた数列の順序を入れ替えても影響はないので、昇順に整列させてペアを数え上げます。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int a[100000];

ll solve(int n) {
    sort(a, a + n);
    ll r = 1;
    ll k = 0;
    ll s = 0;
    bool flag = false;
    for (int i = 0; i < n; i++) {
        if (a[i] <= r) {
            k++;
        } else {
            s += (k * (k - 1)) / 2;
            k = 1;
            while (a[i] > r) {
                r = 2 * (r + 1) - 1;
            }
        }
    }
    s += (k * (k - 1)) / 2;
    return s;
}


int main() {
    int t, n;
    cin >> t;
    ll ans[t];
    for (int i = 0; i < t; i++) {
        cin >> n;
        for (int j = 0; j < n; j++) {
            cin >> a[j];
        }
        ans[i] = solve(n);
    }
    for (ll i : ans) {
        cout << i << "\n";
    }
    return 0;
}