BOJ 2912 | 백설공주와 난쟁이

전승민·2023년 4월 17일

BOJ 기록

목록 보기

5/68

어렵다. Sqrt Decomposition으로 풀려고 했는데 내 머리로는 이 이상 최적화가 안 된다. 8% TLE로 더 이상 진척이 안 된다.

Try 1 (8% TLE)

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
constexpr bool local = true;
#else
constexpr bool local = false;
#endif

#define debug if constexpr (local) std::cout
#define endl '\n'

int N, C;
vector<int> hat;
vector<int> p_hat;
int hatsize[600][10005];
int SIZE_PER_BUCKET;

void divide(){
	map<int, int> counter;
	for (int i = 0; i < N; i++){
		if (i % SIZE_PER_BUCKET == 0 && i != 0){
			// section check pretty
			auto maxpair = *max_element(counter.begin(), counter.end() , [](const auto &x, const auto &y) {
                    return x.second < y.second;
                });
            if (maxpair.second > SIZE_PER_BUCKET/2)
            	p_hat.push_back(maxpair.first);
            else
            	p_hat.push_back(-1);
            counter.clear();
		}
		
		++counter[hat[i]];
		hatsize[i / SIZE_PER_BUCKET][i]++;
	}
	auto maxpair = *max_element(counter.begin(), counter.end() , [](const auto &x, const auto &y) {
                    return x.second < y.second;
                });
    if (maxpair.second > SIZE_PER_BUCKET/2)
    	p_hat.push_back(maxpair.first);
    else
    	p_hat.push_back(-1);
	
}

bool check(int n, int a, int b){
	int total = b-a+1;
	int cnt = 0;
	
	if (n == -1) return false;
	
	// a ~ b 012 345 678 ex) query(1, 8)
	int pstart = a / SIZE_PER_BUCKET;
	int pend = b / SIZE_PER_BUCKET;
	int sk = min( (pstart+1) * SIZE_PER_BUCKET, b+1 );
	for (int i = a; i < sk; i++){ // 12
		if (hat[i] == n) cnt++;
	}
	//debug << n << " debugAA " << cnt << endl;
	
	if (sk != b+1){
		
		for (int i = pstart+1; i < pend; i++){ // (345)
			cnt += hatsize[i][n];
		}
		
		//debug << n << " debugA " << cnt << endl;	
		
		int ek = max( pend * SIZE_PER_BUCKET, a );
		for (int i = b; i >= ek; i--){
			if (hat[i] == n) cnt++;
		}
		
	}
	//debug << n << " debug " << cnt << endl;	
	
	
	if (cnt > total/2) return true;
	else return false;
}

int query(int a, int b){
	set<int> doubt;
	// a ~ b 012 345 678 ex) query(1, 8)
	int pstart = a / SIZE_PER_BUCKET;
	int pend = b / SIZE_PER_BUCKET;
	int sk = min( (pstart+1) * SIZE_PER_BUCKET, b+1 );
	for (int i = a; i < sk; i++){ // 12
		doubt.insert(hat[i]);
	}
	
	//debug << "<>First Check\n";
	//for (auto i : doubt) debug << i << endl;
	//debug << "</>First Check\n";
	
	for (int i = pstart+1; i < pend; i++){ // (345)
		doubt.insert(p_hat[i]);
	}
	
	//debug << "<>Second Check\n";
	//for (auto i : doubt) debug << i << endl;
	//debug << "</>Second Check\n";
	
	int ek = max( pend * SIZE_PER_BUCKET, a );
	for (int i = b; i >= ek; i--){
		doubt.insert(hat[i]);
	}
	
	//debug << "<>Last Check\n";
	//for (auto i : doubt) debug << i << endl;
	//debug << "</>Last Check\n";
	
	for (auto &i : doubt){
		if (check(i, a, b)){
			return i;
		}
	}
	return 0;
	
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	
	cin >> N >> C;
	for (int i = 0; i < N; i++){
		int t; cin >> t;
		hat.push_back(t);
	}
	
	SIZE_PER_BUCKET = sqrt(N);
	divide();
	
	/*
	for (auto i : p_hat){
		debug << i << endl;
	}*/
	
	int M; cin >> M;
	
	for (int i = 0; i < M; i++){
		int a, b; cin >> a >> b;
		int result = query(a-1, b-1);
		if (result == 0) cout << "no" << endl;
		else cout << "yes " << result << endl;
	}
	
}

아 뭔가 생각났는데 내일 풀 예정이다.

그래서 어제 떠오른 아이디어로 check를 최적화했다.
2차원 벡터를 만들어서 [value][idx] 를 넣어 놓고 check 때
이분 탐색으로 hatidx[n]의 lower_bound 와 upper_bound를 구하는 것이다.

Try 2 (19% TLE)

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
constexpr bool local = true;
#else
constexpr bool local = false;
#endif

#define debug if constexpr (local) std::cout
#define endl '\n'

int N, C;
vector<int> hat;
vector<int> p_hat;

vector<vector<int>> hatidx; //[value][idx]

int SIZE_PER_BUCKET;

void divide(){
	map<int, int> counter;
	for (int i = 0; i < N; i++){
		if (i % SIZE_PER_BUCKET == 0 && i != 0){
			// section check pretty
			auto maxpair = *max_element(counter.begin(), counter.end() , [](const auto &x, const auto &y) {
                    return x.second < y.second;
                });
            if (maxpair.second > SIZE_PER_BUCKET/2)
            	p_hat.push_back(maxpair.first);
            else
            	p_hat.push_back(-1);
            counter.clear();
		}
		
		++counter[hat[i]];
	}
	auto maxpair = *max_element(counter.begin(), counter.end() , [](const auto &x, const auto &y) {
                    return x.second < y.second;
                });
    if (maxpair.second > SIZE_PER_BUCKET/2)
    	p_hat.push_back(maxpair.first);
    else
    	p_hat.push_back(-1);
	
}

bool check(int n, int a, int b){
	int total = b-a+1;
	int cnt = 0;
	
	if (n == -1) return false;
	
	cnt = upper_bound(hatidx[n].begin(), hatidx[n].end(), b) - lower_bound(hatidx[n].begin(), hatidx[n].end(), a);
	
	
	if (cnt > total/2) return true;
	else return false;
}

int query(int a, int b){
	set<int> doubt;
	// a ~ b 012 345 678 ex) query(1, 8)
	int pstart = a / SIZE_PER_BUCKET;
	int pend = b / SIZE_PER_BUCKET;
	int sk = min( (pstart+1) * SIZE_PER_BUCKET, b+1 );
	for (int i = a; i < sk; i++){ // 12
		doubt.insert(hat[i]);
	}
	
	//debug << "<>First Check\n";
	//for (auto i : doubt) debug << i << endl;
	//debug << "</>First Check\n";
	
	for (int i = pstart+1; i < pend; i++){ // (345)
		doubt.insert(p_hat[i]);
	}
	
	//debug << "<>Second Check\n";
	//for (auto i : doubt) debug << i << endl;
	//debug << "</>Second Check\n";
	
	int ek = max( pend * SIZE_PER_BUCKET, a );
	for (int i = b; i >= ek; i--){
		doubt.insert(hat[i]);
	}
	
	//debug << "<>Last Check\n";
	//for (auto i : doubt) debug << i << endl;
	//debug << "</>Last Check\n";
	
	for (auto &i : doubt){
		if (check(i, a, b)){
			return i;
		}
	}
	return 0;
	
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	
	hatidx.resize(10001);
	cin >> N >> C;
	for (int i = 0; i < N; i++){
		int t; cin >> t;
		hat.push_back(t);
		hatidx[t].push_back(i);
	}
	
	SIZE_PER_BUCKET = sqrt(N);
	divide();
	
	/*
	for (auto i : p_hat){
		debug << i << endl;
	}*/
	
	int M; cin >> M;
	
	for (int i = 0; i < M; i++){
		int a, b; cin >> a >> b;
		int result = query(a-1, b-1);
		if (result == 0) cout << "no" << endl;
		else cout << "yes " << result << endl;
	}
	
}

19% TLE다. 아까보다는 분명 발전했지만 더 이상 최적화시킬 수단이 떠오르질 않는다. 나는 이걸 평방 분할로 풀 수 없는 것인가.

Try 3 (AC) , 포기하고 랜덤 사용

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
constexpr bool local = true;
#else
constexpr bool local = false;
#endif

#define debug if constexpr (local) std::cout
#define endl '\n'

int N, C;
vector<int> hat;

vector<vector<int>> hatidx; //[value][idx]

bool check(int n, int a, int b){
	int total = b-a+1;
	int cnt = 0;
	
	if (n == -1) return false;
	
	cnt = upper_bound(hatidx[n].begin(), hatidx[n].end(), b) - lower_bound(hatidx[n].begin(), hatidx[n].end(), a);
	
	
	if (cnt > total/2) return true;
	else return false;
}

int query(int a, int b){
	mt19937 engine((unsigned int)time(NULL));
    uniform_int_distribution<int> distribution(a, b);
    auto generator = bind(distribution, engine);
	
	
	for (int i = 0; i < 20; i++){ // 2^20
		int randidx = generator();
		if (check(hat[randidx], a, b)) return hat[randidx];
	}
	return 0;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	
	hatidx.resize(10001);
	cin >> N >> C;
	for (int i = 0; i < N; i++){
		int t; cin >> t;
		hat.push_back(t);
		hatidx[t].push_back(i);
	}
	
	int M; cin >> M;
	
	for (int i = 0; i < M; i++){
		int a, b; cin >> a >> b;
		int result = query(a-1, b-1);
		if (result == 0) cout << "no" << endl;
		else cout << "yes " << result << endl;
	}
	
}

쿼리의 a~b 구간 안에서 무작위 값 하나를 뽑아서 그것이 과반수 이상을 차지하는 수일 확률은 최소 1/2 정도이다.

예를 들어 만약 [1, 1, 1, 1, 1, 2, 2, 3, 5] 인 구간이 있다면 과반수 이상인 1을 뽑을 확률이 5/9이므로 b-a가 커진다면 1/2에 수렴한다고 생각하겠다.

그래서 한 20번정도 무작위로 뽑아서 그 수가 과반수 이상의 비율을 차지하는 지 계산해보고, 맞으면 바로 break 때리고 아니면 계속 돌려보는 것이다.

그렇게 20번 돌렸을 때 오답이 나오는 경우는 어떤 수가 과반수 이상의 비율을 차지함에도 그 수를 뽑지 못하는 경우인데, 이 경우는 (1/2)^20 정도의 확률이므로 (시행 횟수를 늘리면 더 작아진다) 충분히 AC를 맞을 수 있을 거라고 생각했다.

하지만 정말 어떻게든 더 잘 하면 평방 분할로도 풀 수 있을 것 같은데 더 시도해 볼 예정이다.

Try 4 (AC) , 평방 분할

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
constexpr bool local = true;
#else
constexpr bool local = false;
#endif

#define debug if constexpr (local) std::cout
#define endl '\n'

int N, C;
vector<int> hat;
vector<int> p_hat;

vector<vector<int>> hatidx; //[value][idx]

int SIZE_PER_BUCKET;

void divide(){
	map<int, int> counter;
	for (int i = 0; i < N; i++){
		if (i % SIZE_PER_BUCKET == 0 && i != 0){
			// section check pretty
			auto maxpair = *max_element(counter.begin(), counter.end() , [](const auto &x, const auto &y) {
                    return x.second < y.second;
                });
            if (maxpair.second > SIZE_PER_BUCKET/2)
            	p_hat.push_back(maxpair.first);
            else
            	p_hat.push_back(-1);
            counter.clear();
		}
		
		++counter[hat[i]];
	}
	auto maxpair = *max_element(counter.begin(), counter.end() , [](const auto &x, const auto &y) {
                    return x.second < y.second;
                });
    if (maxpair.second > SIZE_PER_BUCKET/2)
    	p_hat.push_back(maxpair.first);
    else
    	p_hat.push_back(-1);
	
}

bool check(int n, int a, int b){
	int total = b-a+1;
	int cnt = 0;
	
	if (n == -1) return false;
	
	cnt = upper_bound(hatidx[n].begin(), hatidx[n].end(), b) - lower_bound(hatidx[n].begin(), hatidx[n].end(), a);
	
	
	if (cnt > total/2) return true;
	else return false;
}

int query(int a, int b){
	set<int> doubt;
	// a ~ b 012 345 678 ex) query(1, 8)
	int pstart = a / SIZE_PER_BUCKET;
	int pend = b / SIZE_PER_BUCKET;
	int sk = min( (pstart+1) * SIZE_PER_BUCKET, b+1 );
	for (int i = a; i < sk; i++){ // 12
		doubt.insert(hat[i]);
	}
	
	//debug << "<>First Check\n";
	//for (auto i : doubt) debug << i << endl;
	//debug << "</>First Check\n";
	
	for (int i = pstart+1; i < pend; i++){ // (345)
		doubt.insert(p_hat[i]);
	}
	
	//debug << "<>Second Check\n";
	//for (auto i : doubt) debug << i << endl;
	//debug << "</>Second Check\n";
	
	int ek = max( pend * SIZE_PER_BUCKET, a );
	for (int i = b; i >= ek; i--){
		doubt.insert(hat[i]);
	}
	
	//debug << "<>Last Check\n";
	//for (auto i : doubt) debug << i << endl;
	//debug << "</>Last Check\n";
	
	for (auto &i : doubt){
		if (check(i, a, b)){
			return i;
		}
	}
	return 0;
	
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	
	hatidx.resize(10001);
	cin >> N >> C;
	for (int i = 0; i < N; i++){
		int t; cin >> t;
		hat.push_back(t);
		hatidx[t].push_back(i);
	}
	
	int M; cin >> M;
	
	SIZE_PER_BUCKET = sqrt(2*M);
	divide();
	
	/*
	for (auto i : p_hat){
		debug << i << endl;
	}*/
	
	
	
	for (int i = 0; i < M; i++){
		int a, b; cin >> a >> b;
		int result = query(a-1, b-1);
		if (result == 0) cout << "no" << endl;
		else cout << "yes " << result << endl;
	}
	
}

어떤 분의 조언을 받아 SIZE_PER_BUCKET을 sqrt(2Q)로 수정하였다. 근데 해놓고 보니까 그 분도 나도 왜 sqrt(2Q)가 최적인지 모르겠다. 이론상으로는 아닌데 왜지? 테스트 케이스의 특수성으로 추측하고는 있다... 아무튼 진짜 왜 맞는지 모르겠다.

전승민

알고리즘 공부한거 끄적이는 곳

이전 포스트

BOJ 2357 | 최솟값과 최댓값

다음 포스트

BOJ 2912 | 백설공주와 난쟁이

BOJ 기록

BOJ 2357 | 최솟값과 최댓값

BOJ 13547 | 수열과 쿼리 5

0개의 댓글