残っているカードのうち、手に入れることのできる確率が最も高いカードを選ぶことが最適であることを示します。以降、\(\frac{A_1}{B_1} \ge \frac{A_2}{B_2} \ge \dots \ge \frac{A_N}{B_N}\) とします。

最終的に自分が得られるカードの枚数の期待値の最大化のみを考えればよいです（証明は後述します）。

\(1\) から \(N\) の順列 \(P\) に対し、以下を戦略 \(P\) ということとします。

• \(1 \le i \le N\) を満たす整数 \(i\) のうち、カード \(P_i\) が残っている最小の \(i\) に対しカード \(P_i\) を選ぶ。

カード \(i\) を先手と後手が永遠に選び続ける場合、先手が取ることができる確率を \(X_i\) とします。ここで、\(\displaystyle X_i = \frac{1}{1+\frac{B_i-A_i}{B_i}}\) です。そして、\(\displaystyle Y_i=\begin{pmatrix} X_i & 1-X_i \\ 1-X_i & X_i \end{pmatrix}\) とします。

\(\displaystyle X_i > \frac{1}{2}\) であるため、\(Y_i\) はどれだけかけても \((1,1)\) 成分が \((1,2)\) 成分より大きいことに注意してください。

先手の取れるカードの枚数の期待値は \(\displaystyle \sum_{i=1}^{N} \prod_{j=1}^{i} Y_j\) の \((1,1)\) 成分です。

もし、\(P_i > P_{i+1}\) である箇所があったらそこを swap します。もし \(\frac{A_{P_i}}{B_{P_i}} > \frac{A_{P_{i+1}}}{B_{P_{i+1}}}\) の場合は \(\displaystyle \prod_{j=1}^{i} Y_j\) の \((1,1)\) 成分が減り、\(\frac{A_{P_i}}{B_{P_i}} = \frac{A_{P_{i+1}}}{B_{P_{i+1}}}\) の場合は \((1,1)\) 成分も勝率も変わらないため、交換するとしてよいです。より命題を示すことができました。

最終的に自分が得られるカードの枚数の期待値の最大化を考えただけでカードの選ぶ順番を決めることができたため、index について上記の証明の仮定で考える必要はありません。

以降、blackyuki 君の勝率を求めることを考えます。

\(\displaystyle Z_i=\begin{pmatrix} (X_i)x & 1-X_i \\ (1-X_i)x & X_i \end{pmatrix}\) とします。\(\displaystyle \prod_{i=1}^{N} Z_i\) を計算することで先手がゲーム終了時に \(i \,(0 \le i \le N)\) 枚のカードを持っている確率を全て求めることができます。二分木のように計算することで計算量 \(\mathrm{O}(N\log^2N)\) で解を求められます。