No.173 カードゲーム(Medium)

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 256 MB / 小数誤差許容問題 絶対誤差または相対誤差が$5 \times 10^{-3}$ 以下
タグ : / 解いたユーザー数 68
作問者 : LayCurseLayCurse
4 ProblemId : 325 / 出題時の順位表
問題文最終更新日: 2015-11-14 17:47:56

問題文

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もしくは右上の雲マークをクリックしてアカウントを作成してください。