BOJ 28245 - 배고파(Hard)

BOJ 28245 - 배고파(Hard)

모든 $(x,y)$ 쌍을 미리 전처리해둔다. 대략 $400$개가 나온다.

이제 $n$개의 테스트케이스마다 그 중에서 가장 가까운 것을 naive하게 찾거나 이분탐색으로 빠르게 찾아서 실수없이 가장 가까운 것을 출력해주면 된다.

void solve() {
   int n;
   cin >> n;

   vector<array<int, 3>> cand;
   for (int i = 0, I = 1; i <= 60; i++) {
      for (int j = i, J = I; j <= 60; j++) {
         cand.pb({I + J, i, j});
         J *= 2;
      }
      I *= 2;
   }
   uniq(cand);

   for (int i = 0; i < n; i++) {
      int m;
      cin >> m;
      array<int, 3> a = {-1, -1};
      array<int, 3> b = {-1, -1};
      array<int, 3> c = {-1, -1};
      for (int j = 0; j < sz(cand); j++) {
         if (cand[j][0] < m) {
            if (a[0] == -1 || cand[j][0] > a[0] || (cand[j][0] == a[0] && cand[j][1] < a[1]))
               a = cand[j];
         } else if (cand[j][0] == m) {
            if (b[0] == -1)
               b = cand[j];
         } else {
            c = cand[j];
            break;
         }
      }
      if (b[0] != -1) {
         cout << b[1] << ' ' << b[2] << endl;
      } else if (a[0] == -1) {
         cout << c[1] << ' ' << c[2] << endl;
      } else {
         if (m - a[0] <= c[0] - m) {
            cout << a[1] << ' ' << a[2] << endl;
         } else {
            cout << c[1] << ' ' << c[2] << endl;

         }
      }
   }
}

빠른 풀이

두 $2$의 거듭제곱수의 합이기 때문에 비트로 표현하면 비트가 항상 두 개가 켜져있거나 한개가 켜져있는 수가 된다.

$m$의 비트수에 따라 케이스워크를 갈긴다

비트 1개

$m=1$ 은 따로 처리를 해주고, 나머지는 $2^{k-1}+2^{k-1}=2^k$ 가 된 것이므로 $m$ 을 그대로 둔다.

비트 2개

그 켜진 비트 두 개가 $x,y$가 된다.

비트 3개

$m$을 줄이거나 늘릴 수 있다.

줄일 경우엔 가장 큰 두 비트를 남기고 버려준다.

$101101 \to 101000$

늘릴 경우엔 두 번째로 큰 비트를 올림해준다.

$101101 \to 110000$

혹은 $110010 \to 1000000$