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를 구하면 된다.
• 확률값 그래프가 구간에 따라 다른 함수를 갖게 되고 스무스하지가 않기 때문에, 수식으로 계산하기는 어렵다. 아니 설령 스무스하더라도 식을 정리해서 한방에 구하기는 어차피 어려울것 같다. 그냥 얌전히 이진검색을 통해서 계산하자. 탐색 범위를 타이트하게 잡으려면, 시작점은 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)

"""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()

• Dependency: teflib.binsearch.maximum_valid_integer