TopCoder, SRM 626, Division 2, Level 2 : FixedDiceGameDiv2

問題文

　http://community.topcoder.com/stat?c=problem_statement&pm=13240&rd=15859

問題概要

　二つのサイコロを使った二人ゲームを考える。Alice は 面のサイコロを、Bob は 面のサイコロを使用する。二人は同時にサイコロを振り、出た目が大きい方のプレイヤーの勝利となる。
　それぞれのプレイヤーが出した目は分からないが、Alice が勝ったことは分かっている。Alice の出目の期待値を求めよ。

解法

　条件付き確率の問題です。条件付き確率は積事象の発生確率を事前条件の発生確率で除すことで求められます。また、期待値は事象の値にその発生確率を乗じた値の総和です。従って、Alice の出目 について考えると、 が出る確率を 、Alice が勝つ確率を とすれば、条件付き確率は となり、期待値は となります。全体の期待値は で表され、変形して です。この式より、事前条件を無視して期待値を求めてから勝利確率で除すことで答えが得られることが分かります。
　では、具体的な確率を求めていきます。出目の期待値は、Alice と Bob の出目をそれぞれ とすれば、 なる について を足し合わせることで計算できます。また、Alice が勝つ確率は同条件の に関して の総和をとった値です。あとは、期待値を勝利確率で割れば全体の答えが求まります。
　 に関する二重ループを回すことで実装するので、計算量は です。

コード

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

class FixedDiceGameDiv2
{
public:
	double getExpectation( int a, int b )
	{
		double res = 0, win = 0;
		REP( i, 1, a + 1 )
		{
			REP( j, 1, b + 1 )
			{
				if ( j < i )
				{
					res += 1. * i / a / b;
					win += 1. / a / b;
				}
			}
		}
		return res / win;
	}
};