[学習記録]AtCoder EDP I-Coins[Go]

問題

N を正の奇数とします。

N 枚のコインがあります。 コインには 1,2,…,N と番号が振られています。 各 i (1≤i≤N) について、コイン i を投げると、確率 pi​ で表が出て、確率 1−pi​ で裏が出ます。

太郎君は N 枚のコインをすべて投げました。 このとき、表の個数が裏の個数を上回る確率を求めてください。

解法

コインがi 枚目が表の時、裏の時を全て計算していると、
保持する値の数が 2 ^N となり、不可能。
i 枚目までのコインを使って、j 枚表が出る確率を保持すると、計算量もN ^2となり、可能になる。

// i番目までで j枚表が出る
for i := 1; i <= n; i++ {
	dp[i] = make([]float64, n+1)
	for j := 0; j <= n; j++ {
		if i < j {
　　　　　   // i 枚までしか使っていないので、i < j となることはない
			break
		}

		pri := sli[i-1]
        // 確率の計算
	}
}

「i枚目まで使って、表の数が j  」となる状態への遷移は、
１．「i -1 枚目まで使って、表の数が j -1」から表がでる
２．「「i -1 枚目まで使って、表の数が j」から裏がでる
の二通りがある。ただし、「i枚目まで使って、表の数がゼロ」となる状態への遷移は、
「i - 1 枚目まで使って、表の数がゼロ」からのみである。
「i -1 枚目まで使って、表の数が j -1」から表がでる確率は、条件付き確率として求められる

pri := sli[i-1]
if j == 0 {
	// i-1番目で0枚の表が出た確率 × i番目で裏がでる確率
	dp[i][j] = dp[i-1][j] * (1.0 - pri)
} else {
	// i-1番目で、j-1枚の表が出た確率 × i番目の表が出る確率
	t := dp[i-1][j-1] * pri
	// i-1番目で、j枚の表が出た確率 × i番目の裏が出る確率
	f := dp[i-1][j] * (1.0 - pri)
　　dp[i][j] = t + f
}

i -1の値を参照することになるが、コインゼロ枚で、表がゼロとなる確率は１００％なので、それをdpにセットする。

dp := make([][]float64, n+1)
dp[0] = make([]float64, n+1)
dp[0][0] = 1

計算がおわったとき、dp[n]が、すべてのコインを使った時、表の出る確率のスライスとなっているので、表の数が上回るしきい値を求め、そこからすべて足し合わせる。

ans := 0.0
majority := n/2 + 1
for i := majority; i <= n; i++ {
	ans += dp[n][i]
}

コード（AC)

func run() interface{} {
	n := readInt()
	sli := readSli(n)

	dp := make([][]float64, n+1)
	dp[0] = make([]float64, n+1)
	dp[0][0] = 1

	// i番目までで j枚表が出る
	for i := 1; i <= n; i++ {
		dp[i] = make([]float64, n+1)
		for j := 0; j <= n; j++ {
			if i < j {
				break
			}

			pri := sli[i-1]
			if j == 0 {
				// i-1番目で0枚の表が出た確率 × i番目で裏がでる確率
				dp[i][j] = dp[i-1][j] * (1.0 - pri)
			} else {
				// i-1番目で、j-1枚の表が出た確率 × i番目の表が出る確率
				t := dp[i-1][j-1] * pri
				// i-1番目で、j枚の表が出た確率 × i番目の裏が出る確率
				f := dp[i-1][j] * (1.0 - pri)
				dp[i][j] = t + f
			}
		}
	}
	ans := 0.0
	majority := n/2 + 1
	for i := majority; i <= n; i++ {
		ans += dp[n][i]
	}
	return ans
}