테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== Marathon ======

===== 풀이 =====
  * 간단한 수식으로 확률을 계산해보자. 
  * 내가 걸린 시간이 t일때, 시간 분포가 [ai,bi]인 i번 선수를 이길 확률은, t<a_i 이면 100%, t>b_i이면 0% 이다. 그리고 a_i<t<b_i 일때 이길 확률은 (b_i-t)/(b_i-a_i) 이다.
  * 이제 1등을 하려면, 모든 상대를 다 이겨야 한다. 1번 선수를 이길확률, 2번 선수를 이길확률, ..., 를 모두 다 곱해주면 1등을 할 확률이 나오고, 이값이 0.5 이상이 되는 t를 구하면 된다.
  * 확률값 그래프가 구간에 따라 다른 함수를 갖게 되고 스무스하지가 않기 때문에, 수식으로 계산하기는 어렵다. 아니 설령 스무스하더라도 식을 정리해서 한방에 구하기는 어차피 어려울것 같다. 그냥 얌전히 [[ps:이진검색]]을 통해서 계산하자. 탐색 범위를 타이트하게 잡으려면, 시작점은 a값들중 최솟값(그것보다 작으면 100% 확률로 1등이다), 끝점은 b값들중 최솟값으로 두면 된다 (그것보다 크면 1등 확률이 0%)
    * 실제 구현에서는, 이것보다는 좀더 널널하게 범위를 잡았다.
  * 실수 범위에서 이분탐색을 돌리는 것은 구현체를 새로 만들어도 안될것은 없지만, 그냥 최대 허용 오차에 맞춰서 정수범위로 바꿔서 돌리는 것이 편하다. 실제로 a,b의 범위는 10^5이지만 허용오차가 10^-6이므로 여기에 10^6을 곱해줘서 계산한다. 탐색 범위는 10^11가 되고, 결정함수를 실행하는 것은 n명의 선수에 대해서 이길확률을 계산해야 하므로 O(n)이 된다. 총 시간복잡도는 O(n*log(m*e)) (m=10^5, e=10^6) 


===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 25280. Marathon".

- Problem link: https://www.acmicpc.net/problem/25280
- Solution link: http://www.teferi.net/ps/problems/boj/25280

Tags: [binary search]
"""

import functools
import sys
from teflib import binsearch

MUL = 10**6


def is_valid(x, ranges):
    prob = 1.0
    for a, b in ranges:
        if x >= a:
            prob *= (b - x) / (b - a)
            if prob < 0.5:
                return False
    return True


def main():
    N = int(sys.stdin.readline())  # pylint: disable=unused-variable
    a_and_b = [
        [float(x) for x in sys.stdin.readline().split()] for _ in range(N)
    ]

    ranges = [(int(a * MUL), int(b * MUL)) for a, b in a_and_b]
    beg, end = min(ranges)
    answer = binsearch.maximum_valid_integer(
        beg, end, functools.partial(is_valid, ranges=ranges)
    )
    print(answer / MUL)


if __name__ == '__main__':
    main()

</dkpr>
  * Dependency: [[:ps:teflib:binsearch#maximum_valid_integer|teflib.binsearch.maximum_valid_integer]]

{{tag>BOJ ps:problems:boj:골드_5}}