과자파티

각 과자를 먹을 확률과 누적합

$i$번 과자를 먹을 지시변수를 $X_i$, 그 과자를 먹을 확률을 $e_i$라 하자. 기댓값의 선형성에 의해 구간 $[l,r]$의 답은

$$\mathbb{E}\left[\sum_{i=l}^{r}X_i\right]=\sum_{i=l}^{r}\mathbb{E}[X_i]=\sum_{i=l}^{r}e_i$$

이다. 서로 다른 과자를 먹는 사건들이 독립일 필요는 없다. 모든 질문은 같은 전체 과정을 기준으로 하므로, $e_i$는 처음부터 한 번만 계산한다.

포만감의 분포 DP

$dp[s]$를 현재 과자를 살펴보기 직전 포만감이 $s$일 확률로 정의한다. 처음에는 $dp[0]=1$이고 나머지는 $0$이다. $i$번 과자에서 상태 일 때 먹을 확률은

$$q_s=\max(0,p_i-0.05s)$$

이므로

$$e_i=\sum_{s=0}^{20}dp[s]q_s$$

이다. 다음 분포 $ndp$를 모두 $0$으로 초기화하고

$$ndp[\min(20,s+1)]\mathrel{+}=dp[s]q_s,$$ $$ndp[\max(0,s-1)]\mathrel{+}=dp[s](1-q_s)$$

를 모든 $s$에 대해 더한다. 이후 $dp$를 $ndp$로 교체한다. 같은 배열을 제자리에서 갱신하면 이번 과자의 결과를 다시 이번 과자의 입력으로 사용하는 오류가 생기므로 두 배열을 분리한다.

$F_0=0$, $F_i=F_{i-1}+e_i$를 저장하면 각 답은 이다. 구간 시작점에서 분포를 초기화해서는 안 된다. 또한 포만감의 평균만 저장하면 일반적으로 충분하지 않다. 먹을 확률의 하한 절단과 포만감 에서의 상태 변화 때문에 평균이 같아도 다음 먹을 확률이나 다음 평균이 달라질 수 있다.

정당성과 복잡도

현재 $dp$가 올바른 분포라고 하자. 주어진 조건부 확률을 곱한 두 전이는 먹는 경우와 먹지 않는 경우를 빠짐없이 나누며, 각각 정확한 다음 포만감으로 확률을 보낸다. 따라서 $ndp$도 올바른 분포이고 $e_i$는 전확률 법칙으로 얻은 실제 먹을 확률이다. 초기 분포가 올바르므로 귀납적으로 모든 $e_i$가 맞다. 기댓값의 선형성과 누적합으로 모든 질문의 답도 맞다.

포만감 상태는 $21$개이다. 시간은 $O(21N+Q)$, 공간은 누적합을 포함해 $O(N)$이다. 질문을 읽는 즉시 출력하면 질문 배열은 저장할 필요가 없다.

작은 입력과 수치 처리

서브태스크 1에서는 $N\leq8$이다. 모든 먹기/건너뛰기 결과를 재귀로 열거하여 정확한 확률을 구할 수 있다. $c_i=100p_i$라 하면 각 단계의 먹기 분자는 $$, 건너뛰기 분자는 에서 이를 뺀 값이다. 모든 결과의 공통 분모는 이다. 결과별 분자 곱을 계산하고, 먹은 각 과자의 분자 합에 더한다. 시간은 , 공간은 이다.

$N\leq8$에서는 분모가 $10^{16}$ 이하, 기댓값 누적합의 분자는 $8\cdot10^{16}$ 이하이므로 signed 64-bit로 정확히 계산할 수 있다. 전체 제한에서는 거대한 정확한 분모를 만들지 않는다. 확률 DP와 누적합에 충분한 정밀도의 실수를 쓰면 된다. 제공한 정해는 입력 확률을 정수 로 읽고, 을 long double로 계산한다. 출력은 소수점 아래 자리이다. 기대 개수는 항상 이상 구간 길이 이하이다.

체커는 유한한 수만 허용하고 $|a-b|\leq10^{-6}\max(1,|b|)$를 검사한다. 여기서 $a$는 제출값, 는 기준값이다. 이는 절대 오차 또는 상대 오차 조건과 같다.

독립 검증

다른 구현은 상태별 확률 대신 누적분포 $C_j=P(S\leq j)$를 갱신한다. $j<20$에 대해

$$C'_j=C_j-P(S=j)q_j+P(S=j+1)(1-q_{j+1}),\qquad C'_{20}=1.$$

또한 $q_{20}=0$이고, 포만감 $0$에서 먹지 않을 때만 보통의 $-1$ 변화가 막힌다. 따라서

$$e_i=\frac{\mathbb{E}[S']-\mathbb{E}[S]+1-P(S=0)(1-p_i)}{2}.$$

평균은 $\mathbb{E}[S]=\sum_{j=0}^{19}(1-C_j)$로 구한다. 이 누적분포와 평균 변화식을 사용하는 구현으로 전체 데이터를 교차검증하고, 작은 입력은 정수 분자를 사용하는 전수검사와도 비교했다.

Solution written by GPT6