[25280] Marathon

난이도: Gold IV

체감 난이도: Silver I + 0.2

 

태그

• Parametric Search (매개변수 탐색)
• Binary Search (이진 탐색)
• Probability Theory (확률론)

 

풀이

1. 특정 사람과 달리기를 했을 때, Erik이 이길 확률은?

어떤 사람이 \( [s, e] \) 시간에 도착하고, Erik은 \( t \)초에 도착한다고 해봅시다.

그럼, 아래와 같은 세 경우에 따라 결정됩니다.

• \( t < s \): 항상 Erik이 이깁니다. 확률로 따지면 \( 1 \)이 되죠.
• \( s \le t \le e \): Erik이 이길 확률은 \( \frac{e-t}{e-s} \)가 됩니다,
  말로 풀어서 쓰면 (어떤 사람이 Erik보다 느리게 도착할 확률) / (전체)가 되겠죠.
• \( e < t \): 항상 Erik이 집니다. 확률로 따지면 \( 0 \)이겠네요.

 

2. 여러 사람들과 달리기를 했을 때, Erik이 1위를 할 확률은?

Erik이 1위를 한다는 건, 다른 모든 사람들을 이겨야 한다는 의미입니다.

사람들의 기록은 서로 독립적이므로, Erik이 \( i \)번째 사람을 \( p_i \)의 확률로 이긴다고 하면

Erik이 모두를 이길 확률은 \( \prod\limits_{i=1}^{N} p_i \)가 됩니다.

 

3. 그래서 50%의 위치는 어떻게 찾지?

[1번]에서 계산한 확률에 의하면, \( t \)가 증가할수록 \( p_i \)는 감소합니다.

그러니, \( \prod\limits_{i=1}^{N} p_i \) 역시 감소하겠죠.

 

다르게 말하자면, Erik이 모두를 이길 확률은 단조함수입니다.

이진 탐색을 돌리기 적절한 구조죠.

 

그러니, Erik이 도착하는 시간 \( t \)를 매개변수로 잡고 모두를 이길 확률에 대해 이진 탐색을 돌리면 됩니다.

 

코드

const ld eps = 1e-8;
inline bool eqf(ld a, ld b){ return abs(a-b)/max<ld>({abs(a),abs(b),1}) <= eps; }
 
inline ld f(ld st, ld ed, ld t){
    if (t <= st){ return 1; } if (ed <= t){ return 0; }
    return (ed-t)/(ed-st);
}
 
pd2 arr[100020];
 
void Main(){
    int n; cin >> n;
    for (int i = 1; i <= n; i++){ cin >> arr[i].fr >> arr[i].sc; }
    ld st = 0, ed = 1e5; while (!eqf(st, ed)){
        ld mid = (st+ed) / 2;
        ld p = 1; for (int i = 1; i <= n; i++){
            p *= f(arr[i].fr, arr[i].sc, mid);
        }
        if (p >= 0.5){ st = mid; } else{ ed = mid; }
    }
    cout << st;
}