Codeforces #348 Div1. C. Little Artem and Random Variable

こちらも誤差死で1WA。
http://codeforces.com/contest/668/problem/C

問題

1～Nの値が出る２つのサイコロがある。
それぞれ各値が出る確率は均等とは限らない。

２つのサイコロを振ったとき、それぞれの目がa,bであるとき、以下の値がx=1～Nそれぞれについて与えられる。
f(x) := max(a,b)=xであるような確率
g(x) := min(a,b)=xであるような確率

元のサイコロについて、それぞれの値が出る確率を求めよ。

解法

xに対し、以下の確率を考える。
a := 1つめのサイコロでx未満が出る確率
b := 2つめのサイコロでx未満が出る確率
p := 1つめのサイコロでxが出る確率
q := 2つめのサイコロでxが出る確率
x := 1つめのサイコロでxより大きい値が出る確率
y := 2つめのサイコロでxより大きい値が出る確率

xを1から順に動かして対応するp,qを求めていくことを考える。
するとp,qを求める際a,bは既知である。またx=1-a-p, y=1-b-qと表せるので、f(x),g(x)は上記の値を用いて以下のように表せる。

f(x) := bp + aq + pq
g(x) := yp + xq + pq = (1-b-q)p + (1-a-p)q + pq = p + q - f(x)

2つ目の式からpとqの関係を求め、1つめの式に代入するとpまたはqの二次方程式ができるのでそれを解けばよい。
誤差で途中確率が負になったりするとWAになるので適宜修正しながら行う。

int N;
long double ma[101010];
long double mi[101010];

long double P[2][101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>ma[i];
	FOR(i,N) cin>>mi[i];
	long double a=0,b=0;
	FOR(i,N) {
		long double na=1-a;
		long double nb=1-b;
		
		long double MM=ma[i]+mi[i];
		long double BB=-(a-b+MM);
		long double CC=-(MM*b-ma[i]);
		long double D=sqrt(max(BB*BB-4*CC,(long double)0.0));
		
		P[1][i]=min(max((long double)0.0,(-BB+D)/2),(long double)1.0);
		P[0][i]=min(max((long double)0.0,MM-P[1][i]),(long double)1.0);
		
		a+=P[0][i];
		b+=P[1][i];
	}
	FOR(i,N) _P("%.12lf%s",(double)P[0][i],(i==N-1)?"\n":" ");
	FOR(i,N) _P("%.12lf%s",(double)P[1][i],(i==N-1)?"\n":" ");
}

まとめ

結構シンプルな問題設定でいいね。