No.173 カードゲーム(Medium)
タグ : / 解いたユーザー数 85
作問者 : LayCurse
問題文
A君とB君はカードゲームが好きである.
このカードゲームでは $1$ から $1000$ までの整数が $1$ つずつ書かれた $1000$ 枚のカードが存在する.
最初にA君とB君にはそれぞれ $N$ 枚ずつカードが配られる.
ゲームはとってもとってもとっても簡単である.
ゲームは $N$ 試合からなる.
各試合では自由にカードを $1$ 枚出して書かれている整数の大きい方がその試合の勝者で,出された $2$ 枚のカードに書かれている整数の和が得点として得られる.
試合で $1$ 度出したカードは $2$ 度使えない.
$N$ 試合が終わった後で得られた合計得点が大きい方がこのゲームの勝者となる(同点なら勝者なし).
カードはすでに配られた状態でA君に配られたカードは $A_1,A_2,\ldots,A_N$ で,B君に配られたカードは $B_1,B_2,\ldots,B_N$ ある.
A君がこのゲームで勝つ確率を計算せよ.
ただし,A君もB君も小さいカードを早めに使用する癖があり,以下の様な方法で各試合に出すカードを選ぶものとする.
A君もB君も,使えるカードが $1$ 枚しかない場合は,必ずそのカードを出す.
A君は,使えるカードが $2$ 枚以上ある場合は,その中で最も小さい整数が書かれたカードを確率 $P_A$ で出し,その他のカードを選ぶ確率は全て等しい.
B君は,使えるカードが $2$ 枚以上ある場合は,その中で最も小さい整数が書かれたカードを確率 $P_B$ で出し,その他のカードを選ぶ確率は全て等しい.
A君も,B君も,今までのゲームの結果,現在のカードの状況等に出すカードは影響されず,それらと独立に出すカードを選ぶ.
入力
$N$ $P_A$ $P_B$ $A_1$ $A_2$ $\cdots$ $A_N$ $B_1$ $B_2$ $\cdots$ $B_N$
$1 \leq N \leq 20$
$0.500 \leq P_A, P_B \leq 0.999$,$P_A,P_B$ はそれぞれ小数点以下高々 $3$ 桁
$1 \leq A_1,A_2,\ldots,A_N,B_1,B_2,\ldots,B_N \leq 1000$
$A_1,A_2,\ldots,A_N,B_1,B_2,\ldots,B_N$ は全て異なる
出力
A君がこのゲームで勝つ確率を出力して下さい.
絶対誤差が $0.005 = 5 \times 10^{-3}$ 以下で正答とみなされる.
サンプル
サンプル1
入力
7 0.873 0.555 97 63 16 83 94 73 55 98 64 17 84 95 74 56
出力
0.310081669035211
B君の方がちょっとずつ高いカードを持っているので,A君はなかなか勝てない!
サンプル2
入力
7 0.999 0.999 97 63 16 83 94 73 55 98 64 17 84 95 74 56
出力
0.001479034961897
B君の方がちょっとずつ高いカードを持っているので,2人共同じように小さい方から出しやすければ,悲しいかなA君はほとんど勝てない!
サンプル3
入力
5 0.5 0.5 1 2 3 4 5 996 997 998 999 1000
出力
0.000000000000000
A君が哀れすぎる!!
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。