概要
解法
公式解説とたぶん違ったので書いておきます．
次の状態を保持するようにします．
- 答が分かっていないカードが $2n$ 枚あり，これらは Flip(i,j) の値が分かっているような $n$ 組の $(i,j)$ に分割されている．
最初は $N$ 回質問することで，$n=N$ に対してこの状態を作ります．
ある異なる $2$ 組 $(i_1,j_1)$, $(i_2,j_2)$ に対して Flip(i,j) がどちらも $x$ に一致するとします．このとき，この $4$ 枚のうちちょうど $2$ 枚が $x$ で，またこれら $4$ 枚のうちで優先度最小のカードが $x$ ということになります．
そこで，$4$ 通りの質問 $(i_p,i_q)$ を行うことでどの $2$ 枚が $x$ であるかを確定させましょう．$x$ ではない返答が返ってくる組み合わせを見ればよいです．
$2$ 枚の答を確定させ，未確定の $2$ 枚については Flip(i,j) が分かっているという状態になります．つまり $n$ がひとつ減少します．
答が未確定であるようなすべての組に対する Flip(i,j) が相異なるとします．このとき，$A_i=A_j=Flip(i,j)$ が成り立ちます．これは，優先度が最大のカードから順に考えることで分かります．
以上をまとめると
- 最初に $N$ 回質問して $n=N$ とする．
- 「$4$ 回質問して$n$ をひとつ減らす」ことを繰り返す．これが行えない場合すべての答えが確定する．
となっています．$n<0$ にはならないため，質問回数は $5N$ 以下となります．
$4$ 回質問するというのは，当たりがちょうど $1$ 個ある $4$ 個のものから当たりを引くためにかかる回数という評価です．ここを乱択で行えば，この部分の質問回数は期待値 $2.5$ 回，問題全体では期待値 $3.5N$ 回以下で解くことができます．
