[백준] 33279. 특식 배분

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

문제 요약

• 특식 N이 주어짐(10만)
• k가 주어짐(N개, i번째 k는 1 ~ i 사이의 정수)
• 특식을 몇개의 생활관이 가져가는지 기대값을 구하는데
• p개가 남았으면 ${1에서 k_p}$ 사이의 랜덤값만큼 가져감(확률 동일)

접근법

• 처음에 문제 이해하기가 어려웠음. 차근 차근 생각해보자
• ${k_p = x}$ 라고 하면
  • 1개를 가져가면 => (p-1의 기대값 + 1) * ${1 \over {k_p}}$
  • 2개를 가져가면 => (p-2의 기대값 + 1) * ${1 \over {k_p}}$
  • ... k_p개를 가져가면 => (p-${k_p}$의 기대값 + 1) * ${1 \over {k_p}}$
  • 들의 합이 p개가 남았을때의 기대값이 된다.
• 식을 잘 보면
  • 모든 합에 ${1 \over {k_p}}$ 이 곱해짐
  • 1은 ${k_p}$ 개만큼 있음
  • p-${k_p}$의 기대값 ~ p-1 기대값까지의 합은 누적합으로 이용 가능!
• 정리하면
  • p개 남았을때의 기대값 = ${1 \over {k_p}}$ * ${(k_p + prefixsum(p-k_p,p-1))}$
  • 그리고 p까지의 누적합을 업데이트