繰り返しの1回(2枚のカードを表にし、スコアを得るかライフが減る)をターンと呼ぶことにします。

ゲームの状態は 「現在のターン中で既に選んだカードの枚数 \(C (\in \{0,1\})\) 、現時点のライフ \(L\)、現在までに獲得したカードの集合 \(S\) 、現時点で(獲得済みを含む)既知のカードの集合 \(T\)」で記述できます。2つの状態 \((C,L,S,T),(C',L',S',T')\) について、\(C=C'\) かつ \(L \leq L'\) かつ \(S \subset S'\) かつ \(T \subset T'\) ならば、\((C',L',S',T')\) の方がよい状況であることに注意します。

取れるカードは常に取るとして損をしません。すなわち、各ターンの1枚目のカードを選ぶ前の時点で、既知のカードでペアができるならその2枚を選ぶとして損をしません。また、1枚目のカードを選んだ後で、その相方が既知であれば、2枚目でペアを作るとして損をしません。

また、既知のカードでペアを作ることができないなら、未知のカードを選ぶとして損をしません。 （なぜなら1枚目で既知のカード、2枚目で未知のカードを選ぶ場合、順序を逆にしても損をしないため1枚目は未知のカードを選ぶとしてよく、またペアを作れる場合を除いて、既知のカードの集合を大きくする方が有利であるため2枚目も未知のカードを選ぶとして良いためです）

以上から、高橋君の最適な行動は、カードに書かれている数に依りません。よって、獲得できるペアの個数の期待値を最大化する戦略により獲得できるペアの個数を \(X\) としたとき、求める答えは \(X \frac{1}{N}\sum A_i\) となります。以下 \(X\) を求める方法を考えます。

\(f(L, C_0, C_1)\) を「ライフが \(L\) で、 \(2(C_0+C_1)\) 枚のカードが場あり、そのうち相異なる数が書かれた \(C_1\) 枚を既知であるとき、このあと取れるペアの個数の期待値」と定めます。

このとき次のターンで起こることは

• \(1\) 枚目の相方が既知で、 \(2\) 枚目にその相方を選ぶ
• \(1\) 枚目の相方が未知で、 \(2\) 枚目にそのカードを引く
• \(1\) 枚目の相方が未知で、 \(2\) 枚目にも相方が未知のカードを引く
• \(1\) 枚目の相方が未知で、 \(2\) 枚目に相方が既知のカードを引く。ライフが残っていれば、この既知のペアを次のターンで獲得する。

の 4 通りのいずれかです。それぞれが起こる確率は容易に計算することができ、それぞれの状況での条件付き期待値は \(f\) を用いて再帰的に表すことができます。

この再帰により \(2C_0+C_1\) は狭義単調に減少するため、 \(f(0,*,*), f(*,0,*)\) を基底ケースとして再帰的に求めることができます。

\(f(L,N,0)\) を求めるためには \(O(LN^2)\) 状態を考慮すればよく、各状態は定数個の遷移を持つので、 \(O(LN^2)\) 時間でこの問題を解くことができました。

なお、メモ化再帰による実装では、定数倍の悪い実装をしてしまうと実行時間制限を超過することがあります。（Writerのメモ化再帰による自然な実装では、pypyで1700ms程度でした）

Writer解(C++)