ARMERIA

Rubyと競技プログラミングの話　AtCoderやCodeforcesの問題解説記事が多め。

エクサウィザーズ 2019 E - Black or White

AtCoder プログラミング競技プログラミング

E - Black or White

解法

答えを定式化する

$i$ 番目のチョコレートを食べ終わった直後に、

黒が残っている確率： $p_{b, i}$
黒白どちらも残っている確率： $p_{bw, i}$

とします。このとき黒だけが残っている確率は $p_{b, i} - p_{bw, i}$ です。

$i$ 番目に食べるチョコレートが黒であるパターンは、

$i-1$ 番目のチョコレートまで食べ終わった直後、黒だけが残っている。
$i-1$ 番目のチョコレートまで食べ終わった直後、黒白どちらも残っていて、 $\frac{1}{2}$ の選択で黒を選ぶ。

のどちらかなので、その確率は $(p_{b, i-1} - p_{bw, i-1}) + \frac{1}{2}p_{bw, i-1}$ で求めることができます。

計算に必要な確率を求める

計算に必要な確率 $p_{b, i}$ と $p_{bw, i}$ を求めましょう。

片方のチョコが切れた後の考え方を簡単にするため、問題を少し言い換えます。

すぬけ君はチョコを1個食べようとするごとに、必ずちょうど1回 黒か白を等確率で選ぶ。選んだ方のチョコがある場合はそちらを食べ、ない場合は選択に関わらず残っている色のチョコを食べる。

この言い換えによって、 $i$ 番目のチョコを食べ終わった直後までに色を選んだ回数が必ず $i$ 回となります。

黒が残っている確率は、この $i$ 回の選択で黒を選んだ回数が $B-1$ 回以下である確率になります。その確率は

$p_{b, i} = (\frac{1}{2})^{i} \times (_{i-1}C_{0} + _{i}C_{1} + \cdots + _{i}C_{B-1})$

となります。

同様に白黒どちらも残っている確率は、黒を選んだ回数が $B-1$ 回以下かつ白を選んだ回数が $W-1$ 回以下である確率になります。黒白の合計が $i$ 回なので、計算すると黒を選んだ回数は $i-(W-1)$ 回以上 $B-1$ 回以下です。その確率は

$p_{bw, i} = (\frac{1}{2})^{i} \times (_{i}C_{i-(W-1)} + \cdots + _{i}C_{B-1})$

となります。（左右それぞれ、 $\lbrack 0, i\rbrack$ の範囲外のものは無視します）

これを全ての $i$ について計算したいのですが、毎回全部計算していては間に合いません。これを計算するためにパスカルの三角形を使います。

頭に付いている $\frac{1}{2}$ の累乗は最後に掛けることにして、二項係数の部分だけ考えます。 $p_{b, i}$ の二項係数の部分を $c_{b, i}$ とします。

f:id:betrue12:20190331094914p:plain

求めたい値は図のように、パスカルの三角形の各段における連続した要素和になります。1つ前の段に注目すると、ほとんどの値については2方向に値が足されるので次の段では2倍されます。唯一 $_{i-1}C_{B-1}$ だけについては、右側の遷移先が範囲外になるので2倍されません。

このことから以下の漸化式が成り立ちます。

$c_{b, i} = 2c_{b, i-1} - _{i-1}C_{B-1}$

$p_{bw, i}$ に対しても同様に、右側に加えて左側についても範囲から外れるところの値を処理することによって、二項係数の和を計算する漸化式を立てることができます。これらの確率が計算できれば、最初に示した式で答えを求めることができます。

ACコード

Submission #4774057 - ExaWizards 2019

有理数を素数modで出力する形式はAtCoderではなかなか見ないですが、Codeforcesではよく見ます。四則演算については割り算として逆元を用いることにして普通に計算すれば大丈夫です。