問題概要
複数のサイコロを使った二人ゲームを考える。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(); } };