TopCoder, SRM 626, Division 1, Level 1 : FixedDiceGameDiv1

問題文

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

問題概要

　複数のサイコロを使った二人ゲームを考える。Alice は 個の 面サイコロを、Bob は 個の 面サイコロを使用する。二人は同時に全てのサイコロを振り、出目の和が大きかったプレイヤーの勝利となる。
　それぞれのプレイヤーが出した目は分からないが、Alice が勝ったことは分かっている。Alice の出目の期待値を求めよ。Alice が絶対に勝てない場合は -1 で示せ。

解法

　まず、Alice が勝てない場合とは、Alice のサイコロの出目が全て であったとしても Bob の出目の最低値 を超えない場合なので、 である場合です。この条件が真のときは -1 を return しておきます。
　さて、次は期待値の求め方です。基本的な方針は Divisin 2, Level 2 と同様に、それぞれの出目の出る確率と出目の値の総和をとってから、Alice の勝利確率で除すことで求めます。ただし、Division 2, Level 2 では出目の確率を のように簡単に書けていましたが、こちらではそうは行きません。ある出目（の総和）が出る確率を計算しておく必要があります。
　出目の確率は、次のように状態をとった動的計画法で求めることができます。

• dp[ i 個のサイコロを振った ][ 出目の和が j ] := 確率

　dp[ i ][ j ] からの遷移は、次のサイコロの出目を全て試して、

• dp[ i + 1 ][ j + k ] += dp[ i ][ j ] / b ( ただし b は Alice の場合。Bob の場合は d )

とします。こうして求めた出目の確率を用いて、Division 2, Level 2 と同じことをやれば答えが得られます。

コード

template < typename T = int > using VT = vector<T>;
template < typename T = int > using VVT = VT< VT<T> >;

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

class FixedDiceGameDiv1
{
public:
	double getExpectation( int a, int b, int c, int d )
	{
		if ( a * b <= c )
		{
			return -1;
		}

		const VT<double> alice = expected( a, b ), bob = expected( c, d );

		double res = 0, win = 0;
		REP( i, 0, alice.size() )
		{
			REP( j, 0, bob.size() )
			{
				if ( j < i )
				{
					win += alice[i] * bob[j];
					res += i * alice[i] * bob[j];
				}
			}
		}
		return res / win;
	}

	VT<double> expected( const int a, const int b )
	{
		VVT<double> dp( a + 1, VT<double>( a * b + 1 ) );
		dp[0][0] = 1;

		REP( i, 0, a )
		{
			REP( j, 0, dp[i].size() )
			{
				if ( dp[i][j] == 0 )
				{
					continue;
				}

				REP( k, 1, b + 1 )
				{
					if ( dp[i].size() <= j + k )
					{
						continue;
					}
					dp[ i + 1 ][ j + k ] += dp[i][j] / b;
				}
			}
		}

		return dp.back();
	}
};