Codeforces Round 846 (Div. 2) - D. Bit Guessing Game (1800)

D. Bit Guessing Game

쿼리가 최대 30회이고 $n \le 10^9$ 이므로 뭔가 한 쿼리당 비트 하나씩 처리해주면 될 것 같은 느낌이 든다.

$1$ 을 빼는것에 중점을 두고 생각한다.

$1$을 뺐을 때 수가 줄어드는 경우는 항상 가장 오른쪽 비트가 $1$인 경우이다.

그렇지 않다면 가장 오른쪽 비트가 $0$ 인 상태였고, 예를 들어, $10000$ 에서 $1$을 빼면 $01111$ 이 되는 것처럼 항상 cnt가 늘어나거나 같아지기 때문이다.

---

101101 이라는 수를 보자.

일단 $1$ 을 뺀다.

101101 cnt = 4

101100 cnt = 3

그리고 $1$ 을 더빼본다.

101100 cnt = 3

101011 cnt = 4

cnt가 1늘어났다. 증감한 개수를 $d$ 라고 하자.

$d=-1$ 라면 가장 오른쪽 비트가 $1$ 인 경우이다.

$d \ge 0$ 이면 이전 수에서 가장 오른쪽 비트가 $0$이였고 첫 번째 비트 왼쪽으로 $d$ 개의 $0$ 이 나온 이후 $1$ 이 있었다는 뜻이다.

그럼 이제 그 $1$은 $0$으로 바뀌었고, 그것보다 작은 모든 비트들은 $d+1$개의 $1$로 이루어진 꼴이 된다.

따라서 $2^{d+1}-1$ 를 $x$ 로 현재 수에서 빼면 그 $1$ 들을 모두 제거할 수 있다.

이렇게 쿼리를 처리하면 $60$ 번 정도 걸리는데, 빠르게 처리하기 위해 이 과정을 합칠 수 있다.

$d \ge 0$ 인 경우에 $2^{d+1}-1$ 를 뺄 것이라고 했는데, 그러면 어차피 첫 번째 자리는 $0$ 이 되므로 거기서 $1$ 을 더 빼버려서 $2^{d+1}$ 을 빼는 쿼리를 날리는 것이다.

단, 현재 cnt=$d+1$ 라면 이번에 빼고 끝이므로 그 과정을 생략해줘야 한다. 그 때는 $2^{d+1}-1$ 만 빼주자.

문제를 풀고 에디토리얼을 봤는데 내가 정리한대로 그냥 처리하면 60번이 걸린다는 내용까지 그대로 나와있어서 좀 놀랐다.

int bcnt(ll x) { return __builtin_popcountll(x); }  
int rz(ll x) { return __builtin_ctzll(x); }  
int lz(ll x) { return __builtin_clzll(x); }  
int msb(ll x) { return 63 - lz(x); }  
  
int n, query_cnt;  
int a;  
  
void init() {  
   query_cnt = 0;  
#ifdef LOCAL  
   cin >> a;  
   debug(bitset<30>(a));  
   n = bcnt(a);  
#else  
   cin >> n;  
#endif  
}  
  
int ask(int x) {  
   int ret;  
   query_cnt++;  
  
   cout << "- " << x << endl;  
  
#ifdef LOCAL  
   a -= x;  
   ret = bcnt(a);  
#else  
   cin >> ret;  
#endif  
   return ret;  
}  
  
void solve() {  
   init();  
  
   int cnt = n, last = n;  
   int sum = 1;  
   last = cnt;  
   cnt = ask(1);  
  
   for (int i = 0; cnt; i++) {  
      int d = cnt - last;  
      if (cnt == d + 1) {  
         int x = (1 << (d + 1)) - 1;  
         sum += x;  
         last = cnt;  
         cnt = ask(x);  
      } else {  
         int x = 1 << (d + 1);  
         sum += x;  
         last = cnt - (d + 1);  
         cnt = ask(x);  
      }  
   }  
   cout << "! " << sum << endl;  
   assert(query_cnt <= 30);  
}