[PS] Latin America 2013 Problem C Counting ones

acm archive

https://icpcarchive.ecs.baylor.edu/index.php?option=comonlinejudge&Itemid=8&page=showproblem&problem=4538

backjoon online judge

https://www.acmicpc.net/problem/9527

PDF file

6527.pdf 다운로드

위영진 학생이 본 문제를 못풀겠다고 해서 풀어주었는데 어려웠다.

솔루션을 찾아봐도 소스를 이해할 수가 없어 새로 생각해 내었는데, 나같은 사람을 위해 풀이를 적는다.

본 문제는 1로 표현된 bit의 개수를 세는데 가장 끝판왕인 알고리즘이다.

정수의 범위가 10^16이라 반복문을 돌면 TLE가 나오기 때문에 일반적은 popbit 알고리즘으로는 본 문제를 풀 수가 없다.

따라서 규칙을 찾아서 바로 해를 찾아야한다.

아래의 표를 먼저 보자

먼저 문제는 A부터 B의 비트의 합이므로, B까지의 누적 비트합에서 A-1의 누적비트합을 빼면 정답이 된다.

위 표에서 누적비트의 수에 적당한 점화식이 생각나지 않으니 2^n인 경우만 따로 뽑아서 보자.

이제 아래와 같은 점화식을 얻을 수 있다.

이제 어떤수 x가 있을때 x보다 작은 2^n의 누적 비트합을 구할 수 있다.

예시를 들면 12의 누적비트합을 구하려고 할때

8의 누적비트합인 13을 먼저 구한다.

그렇다면 이제 9 ,10 ,11 ,12에서의 비트만 구하면 된다. 이는 2진수로 표현한다면 아래와 같다.

이들의 가장 맨 왼쪽의 1비트의 개수는 12-84개이다. 따라서 본 4개를 추가로 더해주고,

12에서 맨 오른쪽 비트를 뺀 1004의 누적비트합을 추가로 더해주면 계산은 끝난다.

아래는 본 솔루션에 대한 소스코드이다.

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.