문제 개요
숫자 n이 주어졌을 때, x = rand() mod n이라고 가정해 보겠습니다. 여기서 rand() 함수는 0부터 10^100까지(양 끝값 포함)의 정수를 균등한 확률로 무작위 생성합니다. 그리고 다음과 같은 무한 중첩 제곱근 형태의 변수 Y가 정의됩니다.
$$Y = \sqrt{x+\sqrt{x+\sqrt{x+\sqrt{x+...}}}}$$
목표는 이 Y의 기댓값을 구하는 것이며, n의 범위는 1 이상 5×10^6 이하입니다.
예를 들어 입력이 n = 5라면 출력은 약 1.696이 됩니다.
핵심 아이디어
무한 중첩 제곱근 Y는 Y² = x + Y를 만족합니다. 이 이차방정식을 풀면 Y = (1 + √(4x+1)) / 2로 정리할 수 있습니다. x는 0부터 n−1까지 균등하게 나타나므로, E[Y]는 결국 f(x) = (1 + √(4x+1)) / 2의 산술 평균이 됩니다.
작은 n에 대해서는 모든 값을 미리 계산해 둔 접두사 합(prefix sum) 배열로 정확한 답을 얻고, 큰 n에 대해서는 적분 근사 공식을 활용해 빠르게 계산하는 전략을 사용합니다.
해결 단계
- 오차 보정값 err := 2235.023971557617로 초기화합니다.
- 최댓값 max_n := 5 × 10^6으로 설정합니다.
- 접두사 합 배열 pref를 만들고 초기값 0을 넣어둡니다.
- i를 1부터 5 × 10^6까지 반복하며, 각 단계마다 (마지막 항목 + (1 + √(4i+1)) × 0.5)를 pref 뒤에 추가합니다.
- n < max_n인 경우, pref[n − 1] / n을 반환합니다.
- 그렇지 않은 경우(큰 n), 근사 공식을 사용합니다.
- total := (4 × (n − 1) + 5)^1.5 / 6 − 5^1.5 / 6 − err
- ans := 0.5 + total / (2 × n)
- ans를 반환합니다.
예제 코드
아래 파이썬 구현을 통해 더 잘 이해할 수 있습니다.
def solve(n):
err = 2235.023971557617
max_n = 5 * 10**6
pref = [0]
for i in range(1, 5 * 10**6):
pref.append(pref[-1] + (1 + (4 * i + 1)**0.5) * 0.5)
if n < max_n:
return pref[n - 1] / n
else:
total = (4 * (n - 1) + 5)**1.5 / 6 - 5**1.5 / 6 - err
ans = 0.5 + total / (2 * n)
return ans
n = 5
print(solve(n))
입력
5
출력
1.69647248786