[Codeforces] Codeforces Round #672 (Div. 2) B. Rock and Lever
問題
方針
自然数 \( 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; }
ディスカッション
コメント一覧
まだ、コメントがありません