SRM練習 626 div1 easy

問題要約：Aはa個の1からbまでの整数が同様に確からしい確率で出るサイコロを持っている。Bはc個の1からdまでの整数が同様に確からしい確率で出るサイコロを持っている。今A,Bがすべてのサイコロをふって自分のサイコロの総和Sa,Sbを求めたところSa>Sbであった。このときSaの期待値を求めよ。

確率DPの部分はできたけど、条件付き確率と期待値計算のところができなかった。

　Aが勝つ確率 PA = Σ_{i>j} (Aの和がiとなる確率)*(Bの和がjとなる確率)

であるので、Aのサイコロの和がxでBに勝つ確率P(x)とすると、

　P(x) = {Σ_{x>j} (Aの和がxとなる確率)*(Bの和がjとなる確率)} / PA

Aが勝つ時のサイコロの和の期待値Eは

　E = Σ x * P(x)

で求まる。
（最初、Bobのサイコロの和を固定して〜とかやっていたら意味不明なことをしてしまった）

#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

double dpA[51][51*51];
double dpB[51][51*51];
class FixedDiceGameDiv1{
public:
	double getExpectation(int a, int b, int c, int d){
		if(a*b <= c) return -1.0;
		for(int j=1; j <= b; j++)
			dpA[1][j] = 1.0 / (double)b;
		for(int j=1; j <= d; j++)
			dpB[1][j] = 1.0 / (double)d;
		for(int i = 2; i <= a; i++)
			for(int j=1; j<=a*b; j++)
				for(int k=1; k<=b; k++){
					if(j-k>=0) dpA[i][j] += dpA[i-1][j-k]/b;
				}
		for(int i = 2; i <= c; i++)
			for(int j=1; j<=c*d; j++)
				for(int k=1; k<=d; k++){
					if(j-k>=0) dpB[i][j] += dpB[i-1][j-k]/d;
				}
		double ans = 0;
		double P = 0;
		for(int SA=a; SA<=a*b; SA++)
			for(int SB=c; SB<=c*d; SB++)
				if(SA > SB){
					P += dpA[a][SA] * dpB[c][SB];
				}
		for(int SA=a; SA<=a*b; SA++)
			for(int SB=c; SB<=c*d; SB++)
				if(SA > SB){
					double p = dpA[a][SA] * dpB[c][SB];
					ans += SA * (p/P);
				}
		return ans;
	}
};