[Python] 25280번 Marathon

https://www.acmicpc.net/problem/25280

25280번: Marathon

---

 

23/08/05

 

 

확률론적인 부분만 해결하면 쉽게 풀 수 있는 이분탐색 문제이다.

---

 

문제 접근 방식:

 

 

문제는 그렇게 길지 않으니 바로 해석을 해보자.

 

$N$명의 다른 참가자들이 언제"쯤" 도착할지를 알려주는 구간 $[a_i, b_i]$가 각 줄마다 입력으로 들어온다.

 

각 참가자들은 이 구간의 어느 한 시각에 "균등한" 확률로 도착한다.

 

우리는 문제의 주인공이 적어도 $50\%$이상의 확률로 우승하는 도착 시각의 최댓값을 구하는 것이 우리의 목적이다.

 

잘 생각해보면, "우승"을 한다는 것은 주인공이 다른 모든 참가자들보다 빠르게 도착한다는 뜻이다.

 

첫 번째 서브태스크를 보면 구간이 겹쳐지지 않는다고 나와있기 때문에, 우리는 $50\%$의 확률로 이기는 도착 시각은 가장 먼저 도착할 것이라 예상되는 한 참가자의 구간 $[a_i, b_i]$의 한가운데 지점이라는 사실을 빠르게 캐치할 수 있다.

 

왜냐하면 가장 먼저 도착할 것이라 예상되는 한 참가자의 구간의 끝 부분 $b_i$보다 주인공이 늦게 도착한다면 주인공은 우승할 가능성이 없기 때문이다.

 

두번째 서브태스크는 구간이 겹쳐있는 상황이다.

 

맨 처음에는 $50\%$의 확률로 우승하는 주인공의 도착 시각을 수식적으로 구해보려고 했으나 잘 되지 않았다.

 

수식적으로 구해보려는 중 한 가지 떠올린 사실은 주인공의 우승 확률을 구하는 것은 곧, 주인공이 모든 참가자들에 대해서 그들보다 빠르게 도착하는 확률을 구하는 것이고, 이는 주인공이 각각의 참가자들에 대해서 그 참가자들보다 빠르게 도착할 확률을 모두 곱한 값이라는 것이었다.

 

따라서 주인공의 도착 시각을 $A$라고 설정하면, 우리는 한 참가자의 도착 시간 구간 $[a_i, b_i]$가 주어져 있고, 그 구간에는 참가자가 균등한 확률로 도착함을 알고 있으므로, 이를 통해 주인공이 한 참가자를 이길 확률을 구할 수 있다.

 

먼저 주인공의 도착 시각 $A$가 $b_i$보다 크다면 주인공은 무조건 지므로, $0$이다.

 

마찬가지로, $A$가 $a_i$보다 작다면 $1$이다.

 

만약 사이에 있다면, 그 확률은 $(b_i - A)/(b_i - a_i)$가 된다.

 

우리는 우승할 확률이 $50\%$가 되도록 하는 $A$를 찾고 싶다. 만약 $A$가 결정된다면, 이 $A$를 통해 이 모든 참가자들에 대해 곱한 값, 즉, 우승할 확률을 구할 수 있다는 사실 또한 알고 있다.

 

따라서 나는 이 사실과 $A$의 값이 크면 클수록 우승할 확률이 낮아지고, 작으면 작을수록 커진다는 사실을 합쳐서 이분탐색을 통해 찾아야겠다는 결론을 얻었다.

 

$A$값을 $mid$로 잡고 이분 탐색으로 구현하였다.   

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 25280번 Marathon
# 이분탐색, 확률론
import sys
input = sys.stdin.readline

N = int(input())
intervals = []
for _ in range(N):
    start, end = map(float, input().rstrip().split())
    intervals.append((start, end, end-start))

start, end = 0, 100_000

while start <= end:
    mid = (start+end)/2
    flag = False
    winning_value = 1
    for interval_s, interval_e, interval_l in intervals:
        if mid > interval_e:
            flag = True
            break
        if mid < interval_s:
            continue
        winning_value *= (interval_e - mid) / interval_l  # 한 사람에 대해 이기는 확률

    if flag:
        end = mid
        continue

    if abs(winning_value - 0.5) < 0.00000001:
        break
    if winning_value > 0.5:
        start = mid
    else:
        end = mid

print(start)