This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.
$maxSide$まであるサイコロを$nDice$個振った時，少なくとも$1$つは$v$が出て，$theSum$を超える確率を求める．
少なくとも$1$つ$v$が出るという条件が無ければ
1
2
3
4
5
6
7
8
dp [ 0 ][ 0 ] = 1.0 ;
rep ( i , nDice ) {
rep ( j , 55 * 55 ) {
REP ( k , 1 , maxSide ) {
dp [ i + 1 ][ j + k ] += dp [ i ][ j ] * ( 1.0 / maxSide );
}
}
}
として，$theSum$以上の和を取れば良いが，この条件がある場合は$v$が出た場合と出ない場合で分ける必要がある．そのためdpを
$$
\begin{eqnarray}
dp[i][j][0] &:=& i個目のサイコロを振って和がjで，一回もvが出ない時の確率 \\
dp[i][j][1] &:=& i個目のサイコロを振って和がjで，少なくとも一回はvが出た時の確率
\end{eqnarray}
$$
として分けて考える．今まで$v$がでなくて，今回初めて$v$が出た時に$[1]$に遷移する．後は少なくとも$1$つ$v$が出る確率を出して割れば良い．この確率は$(1 - vが一回も出ない確率)$として出した．
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair
using namespace std ;
typedef long long ll ;
typedef pair < int , int > P ;
double dp [ 55 ][ 55 * 55 ][ 2 ];
class Conditional {
public :
double probability ( int nDice , int maxSide , int v , int theSum ) {
memset ( dp , 0 , sizeof ( dp ));
dp [ 0 ][ 0 ][ 0 ] = 1.0 ;
rep ( i , nDice ) {
rep ( j , 55 * 55 ) {
REP ( k , 1 , maxSide + 1 ) {
if ( j + k >= 55 * 55 ) continue ;
dp [ i + 1 ][ j + k ][ 1 ] += dp [ i ][ j ][ 1 ] * ( 1.0 / maxSide );
if ( k == v ) {
dp [ i + 1 ][ j + k ][ 1 ] += dp [ i ][ j ][ 0 ] * ( 1.0 / maxSide );
} else {
dp [ i + 1 ][ j + k ][ 0 ] += dp [ i ][ j ][ 0 ] * ( 1.0 / maxSide );
}
}
}
}
double ans = 0.0 ;
REP ( i , theSum , 55 * 55 ) {
ans += dp [ nDice ][ i ][ 1 ];
}
double t = 1.0 ;
rep ( i , nDice ) {
t *= double ( maxSide - 1 ) / maxSide ;
}
return ans / ( 1 - t );
}
};