Back to : algorithms
  • λ‚œμ΄λ„ : Platinum 1
  • 좜처 : Petrozavodsk Summer 2019 Day 3 C
Contents

풀이

$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';
}