問題一覧 > 通常問題

No.174 カードゲーム(Hard)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 256 MB / 小数誤差許容問題 絶対誤差または相対誤差が$10^{-9}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : / 解いたユーザー数 60
作問者 : LayCurseLayCurse
4 ProblemId : 326 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:47:57

問題文

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君がこのゲームで得られる合計得点の期待値を求めて下さい.

ただし,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君がこのゲームで得られる合計得点の期待値を出力して下さい.
絶対誤差または相対誤差が $10^{-9}$ 以下で正答とみなされる.

サンプル

サンプル1
入力
7 0.873 0.555
97 63 16 83 94 73 55
98 64 17 84 95 74 56
出力
398.68259699615

やったね,A君!ちゃんと結構得点は得られるよ!!

サンプル2
入力
7 0.999 0.999
97 63 16 83 94 73 55
98 64 17 84 95 74 56
出力
2.97042774652468

あ,あれ…?
$1$ 試合でも勝てば,最低でも $33$ 点は得られるのに….

サンプル3
入力
5 0.5 0.5
1 2 3 4 5
996 997 998 999 1000
出力
0.000000000000000

やっぱりA君が哀れすぎる!!

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。