https://www.acmicpc.net/problem/18570
원래는 오늘 풀 문제가 있었는데 하루종일 자다보니까 시간이 많이 지나버려서 그냥 눈에띄는거 하나 잡아서 빠르게 쌀먹했다.
일단, 당연히 아무 버스가 도착하는 시간은 모든 버스를 통틀어서 최소 주기보단 작거나 같을 것이다. 이를 T라고 하자. 또한, 아무 버스가 도착하는 시간의 확률변수를 t라고 하자.
P(t>=x)는, 모든 버스가 x분보다 빠르게 도착하지만 않으면 되기 때문에, \( \frac{\prod_{k=1}^n (a_k-x)}{\prod_{k=1}^n a_k}=f(x) \)와 같이 기술할 수 있다. f(x)를 미분하고 -1을 곱하면, 확률밀도함수 p(x)를 얻는다. 기댓값은 xp(x)를 x:0~T까지 적분한 값이라는 사실을 알 수 있다.
f(x)를 구하는 것은 결국 여러 일차식들을 전부 곱하는 문제로 환원되는데, 이는 분할정복과 빠른 다항식 곱셈을 통해서 어렵지 않게 해결할 수 있다. 미분과 적분은 굳이 ps적인 지식을 쓰지 않고도 손쉽게 구현가능하므로 하는법은 생략한다.
P.S.
다음과 같은 요청으로 인해서 일주일에 한번씩 글리젠속도를 낮추기로 하였다. 궁극의 웰노운과 함께 PS일지를 같이 올리도록 하겠다.
