BOJ 2802 - 크레용

BOJ 2802 - 크레용

교육적인 문제라고 생각한다.

$3$차원에서 구간합을 $O(1)$에 구할 수 있다고 해보자.

어떤 채도 $C$에 대해 가능한지 여부는 $C+1$ 로 된 삼차원의 정육면체의 구간합이 $k$ 이상인 곳이 있는지 여부이다.

이건 $O(256^3)$ 에 검사할 수 있고, $C$에 대해선 이분탐색을 할 수 있기 때문에 $O(\log {256} \cdot 256^3)$ 에 문제를 해결할 수 있다.

$3$ 차원 구간합은 그림을 그려보며 식으로 표현하긴 어렵지만 코드는 헷갈리지 않게 구현이 가능하다.

계속 $x,y,z$ 가 하나씩 혹은 두개씩 변경되는 방식으로 표현되기 때문이다.

int psum[260][260][260];  
  
void solve() {  
   int n, k;  
   cin >> n >> k;  
   vector<array<int, 3>> a(n);  
   for (int i = 0; i < n; i++) {  
      cin >> a[i][0] >> a[i][1] >> a[i][2];  
      psum[a[i][0]][a[i][1]][a[i][2]]++;  
   }  
   for (int x = 1; x < 256; x++)  
      for (int y = 0; y < 256; y++)  
         for (int z = 0; z < 256; z++)  
            psum[x][y][z] += psum[x - 1][y][z];  
   for (int y = 1; y < 256; y++)  
      for (int x = 0; x < 256; x++)  
         for (int z = 0; z < 256; z++)  
            psum[x][y][z] += psum[x][y - 1][z];  
   for (int z = 1; z < 256; z++)  
      for (int x = 0; x < 256; x++)  
         for (int y = 0; y < 256; y++)  
            psum[x][y][z] += psum[x][y][z - 1];  
   auto query = [&](int x1, int x2, int y1, int y2, int z1, int z2) {  
      x1--, y1--, z1--;  
      int ret = psum[x2][y2][z2];  
      ret -= z1 >= 0 ? psum[x2][y2][z1] : 0;  
      ret -= y1 >= 0 ? psum[x2][y1][z2] : 0;  
      ret -= x1 >= 0 ? psum[x1][y2][z2] : 0;  
      ret += y1 >= 0 && z1 >= 0 ? psum[x2][y1][z1] : 0;  
      ret += x1 >= 0 && z1 >= 0 ? psum[x1][y2][z1] : 0;  
      ret += x1 >= 0 && y1 >= 0 ? psum[x1][y1][z2] : 0;  
      ret -= x1 >= 0 && y1 >= 0 && z1 >= 0 ? psum[x1][y1][z1] : 0;  
      return ret;  
   };  
   int l = 1, r = 256, ret = -1;  
  
   auto chk = [&](int m) -> bool {  
      for (int x = m - 1; x < 256; x++) {  
         for (int y = m - 1; y < 256; y++) {  
            for (int z = m - 1; z < 256; z++) {  
               if (query(x - m + 1, x, y - m + 1, y, z - m + 1, z) >= k) {  
                  return true;  
               }  
            }  
         }  
      }  
      return false;  
   };  
  
   while (l <= r) {  
      int m = l + r >> 1;  
      if (chk(m)) ret = m, r = m - 1;  
      else l = m + 1;  
   }  
   assert(~ret);  
   int m = ret;  
   cout << m - 1 << endl;  
  
   for (int x = m - 1; x < 256; x++) {  
      for (int y = m - 1; y < 256; y++) {  
         for (int z = m - 1; z < 256; z++) {  
            if (query(x - m + 1, x, y - m + 1, y, z - m + 1, z) >= k) {  
               vi ans;  
               for (int i = 0; i < n && sz(ans) < k; i++) {  
                  if (a[i][0] > x - m && a[i][0] <= x && a[i][1] > y - m && a[i][1] <= y && a[i][2] > z - m  
                     && a[i][2] <= z) {  
                     ans.pb(i);  
                  }  
               }  
               assert(sz(ans) == k);  
               for (int i = 0; i < k; i++) {  
                  int t = ans[i];  
                  cout << a[t][0] << ' ' << a[t][1] << ' ' << a[t][2] << endl;  
               }  
               return;  
            }  
         }  
      }  
   }  
}