백준27470 멋진 부분집합

작성일 | In

문제 링크

  • https://icpc.me/27470

사용 알고리즘

  • 랜덤

풀이

집합의 원소를 아무거나 하나 선택해 봅시다. 만약 문제에서 요구하는 부분 집합이 존재한다면, 임의로 선택한 원소를 포함하는 정답이 존재할 확률이 $50\%$ 이상입니다. 따라서 다음과 같은 성공 확률이 $50\%$ 이상인 알고리즘을 유도할 수 있습니다.

  1. 집합의 원소 $x$를 임의로 하나 선택
  2. $x$의 모든 소인수 $d$에 대해, 집합에서 $d$의 배수의 개수를 카운팅
  3. 만약 $d$의 배수의 개수가 $(N+1)/2$개 이상이라면 출력하고 프로그램 중단

부분 집합이 존재한다면 $x$를 포함하는 정답이 존재할 확률이 $50\%$ 이상이라는 것은, 반대로 말하면 위 알고리즘이 실패할 확률이 $1/2$ 이하라는 의미입니다. 따라서 위 알고리즘을 $K$번 반복하면 정답이 존재하는데 찾지 못할 확률이 $1/2^K$ 수준으로 내려갑니다. 2~30번 정도 반복하면 매우 높은 확률로 문제를 풀 수 있습니다.

전체 코드

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

vector<int> Sieve(int n=40'000){
    vector<int> primes, chk(n);
    for(int i=2; i<=n; i++){
        if(chk[i]) continue;
        primes.push_back(i);
        for(int j=i+i; j<=n; j+=i) chk[j] = 1;
    }
    return primes;
}

int N, K, A[505050], F = 20;
vector<int> P;

vector<int> Factorize(int n){
    vector<int> res;
    for(auto i : P){
        if(i * i > n) break;
        if(n % i != 0) continue;
        res.push_back(i);
        while(n % i == 0) n /= i;
    }
    if(n != 1) res.push_back(n);
    return res;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N; K = (N + 1) / 2; P = Sieve();
    for(int i=1; i<=N; i++) cin >> A[i];

    vector<int> O(N);
    iota(O.begin(), O.end(), 1);
    random_shuffle(O.begin(), O.end());
    if(N > F) O.resize(F);
    for(auto i : O){
        auto V = Factorize(A[i]);
        for(auto d : V){
            int cnt = count_if(A+1, A+N+1, [&](int v){ return v % d == 0; }), rem = K;
            if(cnt < K) continue;
            cout << "YES\n";
            for(int j=1; j<=N && rem>0; j++) if(A[j] % d == 0) cout << A[j] << " ", rem--;
            return 0;
        }
    }
    cout << "NO";
}