ACM-ICPC Latin America 2013 Problem C Counting ones
acm archive
backjoon online judge
PDF file
위영진 학생이 본 문제를 못풀겠다고 해서 풀어주었는데 어려웠다.
솔루션을 찾아봐도 소스를 이해할 수가 없어 새로 생각해 내었는데, 나같은 사람을 위해 풀이를 적는다.
본 문제는 1로 표현된 bit의 개수를 세는데 가장 끝판왕인 알고리즘이다.
정수의 범위가 10^16이라 반복문을 돌면 TLE가 나오기 때문에 일반적은 popbit 알고리즘으로는 본 문제를 풀 수가 없다.
따라서 규칙을 찾아서 바로 해를 찾아야한다.
아래의 표를 먼저 보자
| 숫자 |
1비트의 수 |
누적 비트의 수 |
| 0 |
0 |
0 |
| 1 |
1 |
1 |
| 2 |
1 |
2 |
| 3 |
2 |
4 |
| 4 |
1 |
5 |
| 5 |
2 |
7 |
| 6 |
2 |
9 |
| 7 |
3 |
12 |
| 8 |
1 |
13 |
| 9 |
2 |
15 |
| 10 |
2 |
17 |
| 11 |
3 |
20 |
| 12 |
2 |
22 |
| 13 |
3 |
25 |
| 14 |
3 |
28 |
| 15 |
4 |
32 |
| 16 |
1 |
33 |
먼저 문제는 A부터 B의 비트의 합이므로,
B까지의 누적 비트합에서 A-1의 누적비트합을 빼면 정답이 된다.
위 표에서 누적비트의 수에 적당한 점화식이 생각나지 않으니 2^n인 경우만 따로 뽑아서 보자.
| 숫자 |
1비트의 수 |
누적 비트의 수 |
| 0 |
0 |
0 |
| 1 |
1 |
1 |
| 2 |
1 |
2 |
| 4 |
1 |
5 |
| 8 |
1 |
13 |
| 16 |
1 |
33 |
이제 아래와 같은 점화식을 얻을 수 있다.
a(n)=a(n/2)∗2+(n/2−1)
단n은2의power이다.
이제 어떤수 x가 있을때 x보다 작은 2^n의 누적 비트합을 구할 수 있다.
예시를 들면 12의 누적비트합을 구하려고 할때
8의 누적비트합인 13을 먼저 구한다.
그렇다면 이제
9 ,10 ,11 ,12에서의 비트만 구하면 된다.
이는 2진수로 표현한다면 아래와 같다.
| 10진수 |
2진수 |
| 9 |
1001 |
| 10 |
1010 |
| 11 |
1011 |
| 12 |
1100 |
이들의 가장 맨 왼쪽의 1비트의 개수는 12-8 인 4개이다. 따라서 본 4개를 추가로 더해주고,
12에서 맨 오른쪽 비트를 뺀 100 즉 4의 누적비트합을 추가로 더해주면 계산은 끝난다.
아래는 본 솔루션에 대한 소스코드이다.
long long pop_accumulation_bit(long long x) {
if (x == 0)return 0;
long long r = 1;
int i;
for (i = 0; x >> (i + 1); i++){
r = r * 2 + (1LL << i) - 1;
}
return r + proc(~(1LL << i)&x) + (x - (1LL << i));
}
Copyright (C) 2016 (KimBom) all rights reserved.