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