백준2802 크레용

작성일 | In

문제 링크

  • http://icpc.me/2802

문제 출처

  • 2011/2012 COCI Contest #6 5번

사용 알고리즘

  • 누적합

시간복잡도

  • $O(N + 256^3 \log 256)$

풀이

어떤 값을 최소화하는 문제이니 정답이 $T$ 이하인지 판별하는 파라메트릭 서치를 생각해볼 수 있습니다.

각 크레용을 3차원 좌표 공간 상에서 $(r_i, g_i, b_i)$ 꼴의 점으로 표현할 수 있습니다.
어떤 점 $(x, y, z)$가 있어서, $(x, y, z)$부터 $(x+T-1, y+T-1, z+T-1)$까지의 공간에 $K$개 이상의 점이 판별할 수 있으면 됩니다. 이 결정 문제는 3차원 누적 합을 이용해 $O(256^3)$에 해결할 수 있고, 따라서 전체 문제를 $O(N + 256^3 \log 256)$에 문제를 풀 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
const int m = 256;

int n, k, a[333][333][333];
int r[101010], g[101010], b[101010];

int query(int x, int xx, int y, int yy, int z, int zz){
	int res = a[xx][yy][zz];
	res -= a[x-1][yy][zz] + a[xx][y-1][zz] + a[xx][yy][z-1];
	res += a[x-1][y-1][zz] + a[x-1][yy][z-1] + a[xx][y-1][z-1];
	res -= a[x-1][y-1][z-1];
	return res;
}

int chk(int d, int &x, int &y, int &z){
	for(int i=d; i<=m; i++) for(int j=d; j<=m; j++) for(int k=d; k<=m; k++){
		int t = query(i-d+1, i, j-d+1, j, k-d+1, k);
		if(t >= ::k){
			x = i; y = j; z = k;
			return 1;
		}
	}
	return 0;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> k;
    for(int i=1; i<=n; i++){
    	cin >> r[i] >> g[i] >> b[i];
    	a[++r[i]][++g[i]][++b[i]]++;
    }

	for (int i=1; i<=m; i++) for (int j=1; j<=m; j++) for (int k=1; k<=m; k++){
		a[i][j][k] += a[i-1][j][k] + a[i][j-1][k] + a[i][j][k-1];
		a[i][j][k] -= a[i-1][j-1][k] + a[i-1][j][k-1] + a[i][j-1][k-1];
		a[i][j][k] += a[i-1][j-1][k-1];
	}

	int s = 1, e = m, x, y, z;
	while(s < e){
		int md = s + e >> 1;
		if(chk(md, x, y, z)) e = md;
		else s = md + 1;
	}
	chk(e, x, y, z);
	cout << e-1 << "\n";
	for(int i=1; i<=n && k; i++){
		if(x < r[i] || r[i] < x-e+1) continue;
		if(y < g[i] || g[i] < y-e+1) continue;
		if(z < b[i] || b[i] < z-e+1) continue;
		cout << r[i]-1 << " " << g[i]-1 << " " << b[i]-1 << "\n";
		k--;
	}
}