Codeforces Round #348 C. Little Artem and Random Variable

1 から n の目まであるサイコロが 2 種類ある。このサイコロは出目の確率が均一とは限らない。

このサイコロを同時に振ったときの「目の最小値の確率分布」と「目の最大値の確率分布」が与えられるので、1 つ目のサイコロと 2 つ目のサイコロの確率分布の一例を示せ。

式を立てる都合上、次のように文字を置いておく。

目の最大値が i になるパターンは以下の 3 通り。

よって次のような関係が成り立つ。

$$ M(i) = p(i) q(1..i-1) + p(1..i-1) q(i) + p(i)q(i) $$

目の最小値が i になるパターンは以下の 3 通り。

よって次のような関係が成り立つ。

$$ m(i) = p(i)q(i+1..n) + p(i+1..n) q(i) + p(i)q(i) $$

p(i+1..n)=1-p(1..i-1)+p(i) を用いれば次のように変形できる。

$$ m(i) = p(i)+q(i) - p(i)q(1..i-1) - p(1..i-1) q(i) - p(i)q(i) $$

$$ \begin{align} M(1)&=p(1)q(1) \\ m(1)&=p(1)+q(1)-p(1)q(1) \end{align} $$

という p(1) と q(1) に関する連立方程式を解くことで p(1) と q(1) が得られる。

もし p(1),...,p(i-1) と q(1),...,q(i-1) が求まっていれば、

$$ \begin{align} M(i) &= p(i) q(1..i-1) + p(1..i-1) q(i) + p(i)q(i) \\ m(i) &= p(i)+q(i) - p(i)q(1..i-1) - p(1..i-1) q(i) - p(i)q(i) \end{align} $$

という p(i) と q(i) に関する連立方程式を解くことで p(i) と q(i) が得られる。

したがって i=1 から順に確率を計算できる。

連立方程式を解くのが面倒だったので Wolfram Alpha に投げた。

sqrt に -eps が入らないようにしたけど本当に必要なのかは分からない。

p[0] と q[0] が求まることが割とすぐに分かったので方針が立つのは早かった。はずなのだけど結構時間が掛かっている…。