백준2912 백설공주와 난쟁이

작성일 | In

문제 링크

  • http://icpc.me/2912

문제 출처

  • 2009/2010 COCI #3 5번

사용 알고리즘

  • 랜덤

풀이

주어진 구간 안에서 50번정도 무작위로 뽑은 다음에 절반 이상 차지하는 지 확인해주면 높은 확률로 풀 수 있습니다.

한 번 뽑을 때마다 틀릴 확률이 약 1/2로 줄어들기 때문에, 50번정도 찍으면 틀릴 확률이 약 (1/2)50로 줄어들게 됩니다.

전체 코드

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
#include <bits/stdc++.h>
using namespace std;

int n, q;
int arr[303030];
vector<int> v[10101];

int main(){
	mt19937 rd = mt19937((unsigned)chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> q;
	uniform_int_distribution<int> ran(0, 2147483647);
	for(int i=1; i<=n; i++){
		cin >> arr[i];
		if(v[arr[i]].empty()) v[arr[i]].push_back(-1);
		v[arr[i]].push_back(i);
	}
	cin >> q;
	while(q--){
		int s, e, ans = -1;
		cin >> s >> e;
		for(int i=1; i<=50; i++){
			int j = ran(rd) % (e-s+1) + s;
			int k = arr[j];
			int cnt = upper_bound(v[k].begin(), v[k].end(), e) - lower_bound(v[k].begin(), v[k].end(), s);
			if(cnt > (e-s+1)/2){
				ans = k; break;
			}
		}
		if(ans < 0) cout << "no\n";
		else cout << "yes " << ans << "\n";
	}
}