BOJ 18600, Ptz Camp Summer 2019 Day 3, Valentine's Day

• 난이도 : Platinum 1
• 출처 : Petrozavodsk Summer 2019 Day 3 C

• 풀이
• 코드

풀이

$n$개의 확률이 주어지고, 이들을 모두 더해서 1이라고 할 때, 적당한 subset을 골라서 사건이 단 한 번만 일어날 확률을 최대화하는 문제이다.

사건이 한 번 일어날 확률은 다음과 같이 계산할 수 있다. $S$라는 subset을 골랐을 때, \(\sum_{p \in S} p \prod_{q \in S, q \neq p} (1 - q)\) 그런데, $\prod_{q \in S, q \neq p} (1 - q)$ 는 결국 $\frac{1}{1-p}\prod_{q \in S} (1-q)$ 이므로, 구하는 식은 \(\sum_{p \in S} \frac{p}{1-p} \prod_{q \in S} (1 - q)\) 이제, $\prod_{q \in S} (1 - q) = m_S$ 라 하면 \(m_S \sum_{p \in S} \frac{p}{1-p}\) 를 구하는 문제임을 알 수 있다. 이 $m_S$를 ‘곱 부분’, 뒤 $\sum$ 을 ‘합 부분’ 이라고 부르자.

이렇게 구해진 어떤 집합 $S$에, 새로운 확률 $p’$을 붙이는 것이 이득인지 손해인지를 먼저 따져 보자. 지금까지의 확률을 $p_S$ 라 하고, $p_S$의 합 부분을 $t_S$, 곱 부분을 $m_S$라 하면 $p_S = t_S m_S$이다. 여기서 새로운 확률을 계산하는 것은 어렵지 않은데, 합 부분이 증가하고, 곱 부분에 $(1-p’)$ 를 곱하는 것이므로 \(p_{new} = (1-p')m_S \left(t_S + \frac{p'}{1-p'} \right)\) 이제, $p_{new} - p_S$ 를 계산하면, \(p_{new} - p_S = p' m_S - p' m_S t_S\) 따라서, 이 값이 양수이기 위해서는, $t_S$가 1보다 큰지 아닌지가 중요함을 알 수 있다. $t_S$가 1보다 작다면 새로운 확률값을 집합에 추가했을때 반드시 이득이 되고, 1보다 크다면 반드시 손해가 되기 때문이다.

결국 답이 되는 집합 $S$는, 여기서 하나라도 빼면 $t_S$ 값이 1보다 작아지면서, 현재 $t_S$값이 1보다 큰, 일종의 maximal한 느낌의 집합임을 알 수 있다. (이것을 maximal 이라고 하자) 만약 하나를 뺐을 때 $t_S$ 값이 1보다 여전히 크다면, 그 확률을 빼는 것이 항상 이득이기 때문이다. (추가했을 때 손해였을 것이므로) 이제, 이미 정해진 집합 $S$에서, 확률 $a$를 빼고 대신 $b$를 넣었을 때 득실이 어떻게 변화하는지 생각해 보자. $S$에서 $a$를 뺀 집합 $S_0$ 에 대해, 우리가 비교해야 하는 대상은 $S_0 \cup \Set{a}$ 와 $S_0 \cup \Set{b}$ 를 비교하는 것이다. 그런데, 위 식 $p_{new} - p_S = p’ m_S - p’ m_S t_S$ 을 보면,
$(1 - t_{S_0})$ 값이 양수라면 $p’$가 클수록 이득임을 알 수 있다. 따라서, $S_0 \cup \Set{b}$ 의 확률이 $S_0 \cup \Set{a}$보다 항상 더 크다는 것을 알 수 있다.

따라서, 어떤 maximal 부분집합 $S$에 대해, 여기서 작은 확률값을 제거하고 큰 확률값을 넣는 것은 항상 이득이 되는 연산이다 (maximal 의 정의가, 집합 $S$에서 임의의 확률값 하나를 뺄 때 $t_S$ 값이 1보다 작아지며, 현재의 $t_S$값이 1보다 크거나 같은 집합으로 하였다).

그러므로 Greedy한 접근이 가능하고, 무조건 큰 확률값부터 때려넣으면서 $t_S$값이 1 이상이 되는 순간 멈추는 것이 optimal한 방법임을 알 수 있다. 시간 복잡도는 정렬만 하면 나머지는 $O(n)$에 되기 때문에 $O(n \log n)$.

코드

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define ll long long
#define eps 1e-7
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
#define int ll
using pii = pair<int, int>;

vector <double> probs;

double solve()
{
    probs.clear();
    int n; cin >> n;
    for (int i = 0; i < n; i++)
    {
        double p; cin >> p;
        probs.push_back(p);
    }
    sort(all(probs), greater<double>());
    if (probs[0] >= 0.5)
        return probs[0];
    double s = 0, p = 1;
    for (auto it:probs)
    {
        s += (it / (1 - it));
        p *= (1 - it);
        if (s >= 1) break;
    }
    return s * p;
}

int32_t main()
{
    usecppio
    int t;
    cin >> t;
    while(t--)
        cout << fixed << setprecision(20) << solve() << '\n';
}