[Codeforces]#672B : Rock and Lever(c++)

[문제] : http://codeforces.com/contest/1420/problem/B

[풀이]

배열을 A 에 받았다고 했을 때 A[i]를 기준으로 조건(A[i] & A[j] >= A[i]⊕A[j]) 을 만족하는 수를 찾아보자. A[i]의 최상위 비트만 놔둔채 나머지를 모두 0으로 바꾼수를 tmp 라고 했을 때 조건에 만족하는 수는 tmp ~ A[i] 까지의 수다. 예를 들어 A[i]가 7(111) 일때 최상위 비트만 놔둔채 나머지를 모두 0으로 바꾼수는 4(100)이다. 따라서 4 ~ 7 사이에 있는 수 중에서 A에 있는 수를 계산하면 된다. 이 과정을 빠르게 하기 위해 A를 미리 정렬해 둔 다음 이분탐색을 사용해 index를 찾아 계산하였다.

[코드]

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main(void)
{
	int T;
	cin >> T;
 
	while (T--)
	{
		int n;
		cin >> n;
 
		vector<int> Arr(n);
 
		for (int i = 0; i < n; ++i)
		{
			cin >> Arr[i];
		}
 
 
		sort(Arr.begin(), Arr.end());
		int64_t cnt = 0;
		for (int i = n - 1; i >= 0; --i)
		{
 
			int k = Arr[i];
			int t = k;
			int tmp = t;
			while (1)
			{
				t = ((t &= t - 1));
 
				if (t == 0) break;
				tmp = t;
			}
 
			int p = lower_bound(Arr.begin(), Arr.end(), tmp) - Arr.begin();
 
			cnt += (i - p);
			}
 
		cout << cnt << endl;
	}
}

[느낀점]

처음에 cnt의 자료형을 int 로 했는데 WA를 받았다. 내 풀이가 틀린줄 알고 에디토리얼을 봤는데 전혀 다른 풀이가 나와있었다. 에디토리얼의 풀이는 j를 29부터 0까지 반복하면서 (1 « j) 보다 크거나 같고 (1 « (j+1)) 보다 작은 수의 개수를 찾는 방식이었다. 풀이에 정답을 구하는 변수의 자료형이 int64_t로 되어 있어서 내 풀이의 자료형을 바꿔 보았더니 AC를 받을 수 있었다.

지적 환영합니다