Codeforces Round #341 (Div. 2) C. Wet Shark and Flowers

問題概要

i 番目の人が持つ値 s_i は [l_i, r_i] からランダムに選ばれる。 i 番目が貰える金額は（次のうち満たした条件の数）×1000ドルである。

s_i-1 * s_i が p の倍数
s_i * s_i+1 が p の倍数

1, ... , n 番目の人がもらう金額の合計の期待値を求めよ。ただし p は素数。

解法

期待値の線形性より、1, ... , n 番目の人がもらう金額の合計の期待値は、i 番目の人がもらう金額の期待値の合計になる。

$X_i$ を $i$ 番目の人がもらう金額とすれば、求めるのは $X_1+\cdots+X_n$ の期待値になる。期待値には線形性があるので $$ E[X_1+X_2+\cdots + X_n] = E[X_1]+E[X_2]+\cdots + E[X_n] $$ が成り立つ。

$s_{i-1}s_i$ が $p$ の倍数のとき、$s_{i-1}$ と $s_i$ のどちらか一方は $p$ の倍数になる。そのため $s_i$ が $p$ の倍数になる確率を $q_i$ とすれば、$s_{i-1}s_i$ が $p$ の倍数になる確率は $q_{i-1}+q_i-q_{i-1}q_i$ と表せる。 i と i+1 も同様。

したがって、

$$ E[X_i]= 1000(q_{i-1}+q_i-q_{i-1}q_i) + 1000(q_i+q_{i+1}-q_iq_{i+1})$$

になる。後は足し合わせるだけ。

Codeforces Round #341 (Div. 2) C. Wet Shark and Fl ...

期待値は苦手だけどこれはすぐ解けた。