Francis Galton은 중심 극한 정리 중 충분한 표본 크기에서 이항분포가 정규분포에 근접한다는 것을 증명하기 위해 갈톤보드를 발명하였다. 갈톤보드는 보드와 보드에 수직으로 세워진 못으로 구성되어 있다. 위에서 구슬을 떨어뜨리면 여러 줄의 못과 부딪혀 왼쪽 또는 오른쪽으로 튕겨 나가는 과정을 반복한다. 바닥에 도착한 구슬은 칸막이에 의해 나눠지며 일반적인 갈톤보드는 위와 같이 정규분포를 보인다. 하지만 이상한 나라의 이상한 갈톤보드는 시작지점에서 도착가능한 모든 지점에 동일한 확률로 떨어진다. 모든 도착지점에 비슷한 개수의 구슬이 떨어지면 재미없기 때문에 구슬을 떨어뜨리는 시작지점을 선택할 수 있게 만들었다.
높이가 5인 이상한 갈톤보드의 시작지점과 도착지점 번호는 위와 같은 규칙을 가진다.
만약 시작지점 2에서 떨어뜨린다면 도착지점 [1, 5]에 모두 같은 확률로 도착한다. 만약 시작지점 6에서 떨어뜨린다면 도착지점 [3, 6]에 모두 같은 확률로 도착한다.
이상한 나라의 앨리스는 이상한 갈톤보드에 구슬을 떨어뜨리고 도착지점의 구슬 개수를 세려고 했지만 구슬이 너무 많아 포기했다. 대신 도착지점의 구슬 개수 기댓값을 구해 개수를 추측하려고 한다. 앨리스를 도와 구슬의 기댓값을 출력하는 프로그램을 작성하자.
프로그램은 두 쿼리를 수행한다. 구슬을 떨어뜨리는 쿼리가 Q개 주어진다. a, b : a번째 시작지점에 b개의 구슬이 떨어진다. 모든 구슬이 떨어진 후 도착지점에 존재하는 구슬 개수의 기댓값을 구하는 쿼리가 R개 주어진다. a, b : 도착지점[a, b]에 떨어지는 구슬 개수의 기댓값을 출력한다. 프로그램은 기댓값 쿼리를 모두 처리한 후 종료한다.
둘째 줄에는 구슬을 떨어뜨리는 쿼리의 개수 Q와 기댓값을 묻는 쿼리의 개수 R이 주어진다. (1 <= Q <= 100,000, 1 <= R <= 100,000)
셋째 줄부터 Q개의 쿼리 a, b가 주어진다. (1 <= a <= H * (H+1) / 2, 1 <= b <= 100,000)
3 + Q번째 줄부터 R개의 쿼리 a, b가 주어진다. (1 <= a <= b <= H + 1)
출력
각 쿼리의 결과를 순서대로 한 줄에 하나씩 출력한다.
절대/상대 오차는 10^-4까지 허용한다.
입력 예시
5
2 3
2 15
6 12
1 2
3 5
6 6
출력 예시
6.0
18.0
3.0
풀이
우선, R의 쿼리는 구간의 기댓값 합을 요구하고 있다. 따라서 빠른 쿼리 처리를 위해 누적합 배열을 사용해 봄직하다. 누적 기댓값 리스트가 N이라면, a, b 구간의 누적합은 N[b] - N[a-1] 이 될 것이다.
이제 누적합을 사용한다는 점을 염두해 두고, Q개 쿼리로 돌아가보자. 우리가 i번째 시작지점에서 공을 떨어뜨린다면, i번째 시작지점의 높이를 구해야 한다. (높이가 높을수록 공이 떨어지는 구간이 넓어진다) 높이가 최대 H이고 1 <= H <= 100,000이므로 높이를 빠르게 찾아야 한다. 이 역시 누적합 배열과 이분 탐색으로 빠르게 찾아볼 수 있다.
j번째 높이 구간의 높이는 H-j+1가 되고(1 <= j <= H), 이는 공이 떨어지는 시작 구간에서 종료 구간까지의 거리와 동일하다.
또한 j번째 높이 구간의 가장 오른쪽 원소는 j*(j+1) / 2임이 보장된다. 이는 1부터 j까지의 합과 동일하다.
따라서, 오른쪽 원소 구간을 저장한 누적합 배열을 이분 탐색으로 서칭하면 높이를 O(logH) 시간복잡도로 구할 수 있다.
우리는 기댓값을 업데이트해야 하므로, 구간의 구슬은 (전체 구슬 / 구간 길이)로 나뉘어 떨어질 것이다. 즉 시작 지점에 그 기댓값을 +하고, 종료 지점 다음에 기댓값을 -한다. 이는 나중에 O(H) 시간복잡도로 일반 기댓값 리스트 및 누적합 리스트로 변환 가능하다. 총 시간복잡도는 O(QlogH + H + R)이 된다.
풀이 코드
import bisect
import sys
input = sys.stdin.readline
H = int(input())
Q, R = map(int, input().split())
sum_list = [0]
for i in range(H) :
sum_list.append(sum_list[-1]+i+1)
updates = [0.]*(H+2)
for _ in range(Q) :
a, b = map(int, input().split())
idx = bisect.bisect_left(sum_list, a)
start = a - sum_list[idx-1] - 1
end = start + (H - idx + 1)
updates[start] += b / (end - start + 1)
updates[end+1] -= b / (end - start + 1)
result = [0.]*(H+2)
for i in range(1, H+2) :
result[i] = result[i-1] + updates[i-1]
for i in range(1, H+2) :
result[i] += result[i-1]
for _ in range(R) :
a, b = map(int, input().split())
print(result[b] - result[a-1])
