お菓子パーティー

食べる確率と累積和

$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$、他は零である。$i$ 番での条件付き確率を

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

とすると

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

となる。次の分布 $ndp$ をすべて零にし、各 $s$ について

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

を加える。その後 $dp$ を $ndp$ に置き換える。同じ配列をその場で更新すると、今回の結果を今回の入力として再利用してしまうので、二つの配列を分ける。

$F_0=0$、$F_i=F_{i-1}+e_i$ を保存すると、各答えは となる。区間の左端で分布を初期化してはいけない。また平均満腹度だけの保持も一般には不十分である。確率の零での切り捨てと満腹度零の境界により、その後の挙動は平均だけでなく分布に依存する。

正当性と計算量

現在の $dp$ が正しい分布だとする。二つの遷移は各状態確率に指定の条件付き確率を掛け、食べる場合と食べない場合を漏れなく分けて、正しい次の満腹度へ送る。よって $ndp$ は正しく、全確率の公式から $e_i$ も正しい。初期分布が正しいので帰納的にすべての確率が正しく求まる。期待値の線形性と累積和から各質問の答えも正しい。

状態は 21 個である。時間は $O(21N+Q)$、累積和を含む空間は $O(N)$ となる。質問は読み込んだ直後に答えれば保存する必要がない。

小さい入力と数値計算

サブタスク 1 は $N\leq8$ である。食べる・食べないの全結果を再帰で列挙できる。$c_i=100p_i$ とすると各段階の食べる確率の分子は $$、食べない確率の分子は 100 からそれを引いた値である。全結果の共通分母は となる。各結果の分子の積を、その結果で食べた各お菓子の分子和に加える。時間は 、空間は である。

分母は最大 $10^{16}$、期待値の累積和の分子は最大 $8\cdot10^{16}$ なので、符号付き 64 ビット整数で正確に求められる。全体の制約では巨大な厳密分母を作らず、十分な精度の浮動小数点数を使う。主解法は確率を整数 $c_i$ として読み、 を long double で計算して小数点以下 15 桁を出力する。期待個数は常に零以上、区間長以下である。

チェッカーは有限の数だけを許し、提出値 $a$、基準値 $b$ に対して $|a-b|\leq10^{-6}\max(1,|b|)$ を確認する。これは指定された絶対誤差または相対誤差の条件と等価である。

独立検証

別実装は状態確率ではなく累積分布 $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$ であり、通常のマイナス一の変化が起きないのは満腹度零で食べない場合だけなので

$$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