10/03/29 06:52:40
>>161
n種類,2n枚のカードが場にあり、m回までミスが許され、
種類の異なる k枚のカードの位置を知っているとき、
クリアできる確率を a[n,m,k] とすると、
a[n,m,k] = (k/(2n-k)) * a[n-1,m,k-1]
+ ((2n-2k)/(2n-k)) * (1/(2n-k-1)) * a[n-1,m,k]
+ ((2n-2k)/(2n-k)) * (k/(2n-k-1)) * a[n-1,m-1,k]
+ ((2n-2k)/(2n-k)) * ((2n-2k-2)/(2n-k-1)) * a[n,m-1,k+2]
が成立して、これを
a[n,-1,k] = 0,
a[0,m,0] = 1 (m≧0)
の境界条件で解く
求める確率は a[n,m,0]
n=6, m=3: 1459/2079 = 70.17797%
n=6, m=2: 467/3465 = 13.47763%
n=6, m=0: 1/10395 = 0.00962%
n=12, m=8: 104092005923/105411381075 = 98.74836%
n=12, m=6: 99957668383/316234143225 = 31.60875%
n=12, m=5: 870234203/21082276215 = 4.12780%
n=24, m=18:
218697824447990693116147097/218699466857589239600203125 = 99.99925%
n=24, m=15:
348744131067430903257805643/387827054560791584891026875 = 89.92259%
n=24, m=12:
51728468019179261601543475781/1192568192774434123539907640625 = 4.33757%