\(N\) 本先取なので、試合の決着がつくまでに行われるゲームの回数は高々 \(2N-1\) 回です。 \(i = 1, 2, \ldots, 2N-2\) について確率変数 \(X_i\) を、

• 勝負がつくまでにゲームが \(i+1\) 回以上行われ、かつ、\(i\) ゲーム目と \(i+1\) ゲーム目の \(2\) ゲームによって「逆転」が起きた場合、\(X_i = 1\) 、
• そうでない場合、\(X_i = 0\)

をとる確率変数とします。 このとき、試合の決着がつくまでに起こる「逆転」の回数は \(\sum_{i = 1}^{2N-2} X_i\) です。 よって、本問題の答えはその期待値 \(E[\sum_{i = 1}^{2N-2} X_i]\) です。 これは、期待値の線形性より \(\sum_{i = 1}^{2N-2} E[X_i]\) と等しいので、 本問題を解くには、\(i = 1, 2, \ldots, 2N-2\) について \(E[X_i]\) の値がわかれば良いです。

\(E[X_i]\) は確率変数 \(X_i\) の定義より 「勝負がつくまでにゲームが \(i+1\) 回以上行われ、かつ、\(i\) ゲーム目と \(i+1\) ゲーム目の \(2\) ゲームによって「逆転」が起き」る確率と等しいのでこの確率がわかれば良いです。 \(i\) ゲーム目と \(i+1\) ゲーム目の \(2\) ゲームによって逆転が起きることは、

1. \(i\) ゲーム目終了時の両者の勝利回数が等しく、
2. \(i+1\) ゲーム目の勝者は \(i\) ゲーム目の勝者と等しい

ことと同値です。\(i\) が奇数の時は、明らかに上記の条件 1. を満たし得ないので \(E[X_i] = 0\) です。 以下、\(i\) が偶数と仮定します。 このとき、条件 1. は、\(i\) ゲーム目終了時点の両者の勝利回数がそれぞれ等しく \(i/2\) 回であることと同値であり、そうなる確率は二項係数を用いて

\[\binom{i}{i/2}\times\Big(\frac{1}{2}\Big)^i\]

とかけます。また、条件 2. が成り立つ、すなわち、\(i+1\) ゲーム目の勝者が \(i\) ゲーム目の勝者と等しい確率は \(\frac{1}{2}\) です。

よって、上記の条件 1. と条件 2. が同時に満たされる確率は

\[\binom{i}{i/2}\times\Big(\frac{1}{2}\Big)^{i+1}\]

です。\(i = 1, 2, \ldots, 2N-2\) を考える限り、「上記の条件 1. を満たす、すなわち、\(i\) ゲーム目終了時点の両者の勝利回数がそれぞれ等しく \(i/2\) 回である」ならば、「 \(i\) ゲーム目終了時点ではどちらの勝利回数もまだ \(N\) 回に達しておらず、勝負がつくまでにゲームが \(i+1\) 回以上行われる」ことに注意してください。 以上より、\(i\) が偶数の場合は、

\[E[X_i] = \binom{i}{i/2}\times\Big(\frac{1}{2}\Big)^{i+1}\]

となります。

上の議論より本問題の答えは、

\[\sum_{\substack{i = 1\\i \bmod2 = 0}}^{2N-2} E[X_i] = \sum_{j = 1}^{N-1}\binom{2j}{j}\times\Big(\frac{1}{2}\Big)^{2j+1}\]

です。

階乗の適切な前計算によって必要な二項係数をそれぞれ \(\mathrm{O}(1)\) 時間で求められるようにしておくことで、上記の答えは \(\mathrm{O}(N)\) 時間で求めることができます。