Alice の初手は、Bob が \(\min B\) を選んだ場合に対応できるように選ぶ必要があります。そのような \(A_i\) が複数ある場合、その中で最大の要素 \(A^*\) を選ぶものとして構いません。

証明

Alice が初手に \(A^*\) を選ぶと負けるが、\(\hat{A}\) を選ぶと勝てると仮定して矛盾を導きます。Bob が \(\min B\) を選んだ場合を考えれば、\(\hat{A} \lt A^*\) です。

Alice が \(A^*\) を選んだ場合の Bob の手を \(B^*\) と置きます。

\(A^* \geq B^*\) の場合

\(A^*\) は \(\min B\) に対して勝てるように選んだので、残ったカードの中に \(A^*-\min B \lt A_k \lt A^*+\min B\) を満たす \(A_k\) が存在します。これは \(A^* - B^* \lt A_k \lt A^*+B^*\) も満たすので、Alice が勝ち、矛盾します。

\(A^* \lt B^*\) の場合

Alice は \(\hat{A}\) を選ぶと勝つので、\(B^* -\hat{A} \lt A_k \lt B^*+\hat{A}\) を満たす \(A_k\) が存在します。もし \(A_k = A^*\) ならば、Alice が初手に \(A^*\) を選び Bob が \(B^*\) を選んだ場合に \(\hat{A}\) を選べば Alice が勝つので矛盾します。\(A_k \neq A^*\) ならば、同じ状況で \(A_k\) を選べば Alice が勝つので (\(\hat{A} \lt A^*\) を用いました) こちらも矛盾します。

Bob の手を全探索し、それに対する Alice の 2 手目が存在するかどうかを二分探索などで確認すれば \(\Theta (N \log N)\) の時間計算量のアルゴリズムが得られます。