pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Codeforces Round #348 C. Little Artem and Random Variable

http://codeforces.com/contest/668/problem/C

問題概要

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

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

解法

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

  • M(i) := 目の最大値が i になる確率
  • m(i) := 目の最小値が i になる確率
  • p(i) := 1 つ目のサイコロで i が出る確率
  • q(i) := 2 つ目のサイコロで i が出る確率
  • X := サイコロ 1 の目
  • Y := サイコロ 2 の目

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

  1. X=i かつ Y≦i-1
  2. X≦i-1 かつ Y=i
  3. X=Y=i

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

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

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

  1. X=i かつ Y≧i+1
  2. X≧i+1 かつ Y=i
  3. X=Y=i

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

$$ 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 が入らないようにしたけど本当に必要なのかは分からない。

Codeforces Round #348 C. Little Artem and Random V ...

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