우체국 4 풀이

www.acmicpc.net/problem/18445

18445번: 우체국 4

우체국 3의 풀이는 안다는 가정 하에 설명한다.

우체국 3의 풀이는 원형구간에 대한 풀이를 각 점을 시작으로 한 선형구간에 대해 문제를 푸는 것을 N번 반복하여 문제를 풀어낸다. 이렇게 하여 시간복잡도는 O(N^2KlogN)이다.

하지만 굳이 N개를 다 잘라보는 것은 뭔가 손해같다.

특히 K가 클 때 시간이 오래 걸리는데 이때는 분할되는 갯수가 많아서 optimal한 시작점이 최소 K개나 존재한다!!

그러므로 우리는 K가 클 때는 좀 더 적은 점들에서만 잘라봐도 문제가 풀릴 것임을 알 수 있다.

만약 x개의 지점을 잘라본다면 이 중 최적의 위치가 있을 확률은 최소 1-(1-K/N)^x이다. 그리고 이때 소모되는 시간은 O(NKxlogN)이다. K가 크나 작으나 시간이 거의 균등하게 하기 위해서 x=(N/K)*a로 잡자. 시간복잡도는 O(N^2logN*a)가 되고 우리는 이 a를 WA와 AC 그리고 TLE 사이에서 적절히 조절해주면 된다. 1-(1-K/N)^x를 이렇게 바꾸면 1-(1-K/N)^((N/K)*a)가 된다. 매개변수 y를 잡아 y=K/N이라 하자. 0<y<<=1이고 답이 맞을 확률은 1-(1-y)^(a/y)이다. 이때 답이 틀릴 확률은 ((1-y)^(1/y))^a이고 a는 논외로 하고 (1-y)^(1/y)의 그래프를 보자.

y가 작은 시점에서 1/e 정도의 값을 가지는 것이 최대임을 알 수 있다. 그러므로 a를 적당히 늘려 답이 틀릴 확률이 거의 없게 해주자. a=10 정도라면 답이 틀릴 확률은 4.5*10^-5 정도로 굉장히 낮아진다. 이때 2500 엔제곱로그는 1초에 도니까 2500 엔제곱로그 곱하기 10도 10초 안에는 돌 거라는 것을 추측할 수 있고 제출하면 AC를 받을 수 있다.

굉장한 날먹 풀이다. 왠지 사람들이 이해하게 된다면 어 쉬운데? 하면서 이 문제의 티어가 깎여나가는 엔딩을 겪게 될 거 같은데 너무 슬프다.