準備

箱から取り出す順に，ボールの番号を \(P_1,P_2,\dots, P_N\) とします. ここで \(P\) は \((1,2,\dots, N)\) の順列で，\(N!\) 通りある \(P\) がどれも等確率で現れます. そこで，ゲームを始める前に \(P\) があらかじめ一様ランダムに選ばれて固定されているとし，ゲームの最中に先頭の項から順に明らかになるという設定だと思うことにします.

以降，ボールのことは忘れて番号のみに注目します. \(2\) つの番号の和が \(M\) 未満であるとき，それらの番号はペアにできるといいます. ペアにできない \(2\) つの番号が手元にある状態に一度でもなると，スコアが \(0\) になります. スコアが \(0\) でないとき，最終的に手元に残った番号がスコアを与えます.

最適な戦略とスコア

Alice が選択できるのは，手元にある \(2\) つの番号のうちどちらを残すか，です. この選択は \(N-1\) 回行われます. 選択する際には，それまでに取り出した番号の集合を参照できることに注意してください.

Alice の最適な戦略は次のように与えられます. 手元にある番号を \(x\lt y\) とします.

• まだ現れていない番号のうち，\(y\) とペアにできないものが存在しないなら，\(y\) を残す
• そうでないなら，\(x\) を残す

最適性は，\(P\) をすべて知っている状態でゲームをしてもこの戦略が最適になることから従います. 実際，この戦略に従って得られるスコアは

• ある \(i\in [2,N]\) が存在して，どの \(j\lt i\) に対しても \(P_j\) が \(P_i\) とペアにできないとき，スコアは \(0\)
• そうでないときのスコアは，どの \(j\gt i\) に対しても \(P_j\) が \(P_i\) とペアにできるような \(P_i\) の最大値

であり，\(P\) を知っていてもこれを超えることはできません. 以降，戦略のことは忘れて，順列 \(P\) が上述のスコアを定めるものとします. また，スコアは決定的に定まるため，期待値ではなく単にすべての順列 \(P\) に対するスコアの総和を計算したあと，最後に \(N!\) で割ることにします.

挿入 DP

\(M\le N+1\) のとき，\(N\) はどの番号ともペアにできないので答えは \(0\) です. \(M\ge 2N\) のとき，どの \(2\) つの番号もペアにできるので答えは \(N\) です. 以降，\(N+2\le M\le 2N-1\) を仮定します. スコアの総和を求める上では，スコアが \(0\) でないような \(P\) についてのみ考えればよいです.

各番号 \(i\) に次のようにラベルをつけます.

• \(1\le i\lt M/2\) のとき：A
• \(M/2\le i\le N\) のとき：B

B の番号どうしはペアにできません. したがって，\(P_1,P_2\) の少なくとも一方は A の番号です. また，\(P_1,P_2\) を入れ替えてもスコアは変わりません. そこで，以降は \(P_1\) が A の番号であるもののみを考え，\(P_2\) が B の番号である場合は答えに \(2\) 倍寄与させることにします.

空列から始め，ある順番で番号を好きな位置に挿入することを繰り返すことを考えます. 以降，その順番において出現する番号の相対的な位置関係には「先」「後」という表現を用い，\(P\) においては「左」「右」という表現を用います. さて，まずは次の \(N=20,M=30\) の例を見てください.

1,2,3,4,5,6,7,8,9,20,10,19,11,18,12,17,13,16,14,15
A,A,A,A,A,A,A,A,A,B ,A ,B ,A ,B ,A ,B ,A ,B ,A ,B 

上の行は挿入する番号の順番，下の行はそれらの番号のラベルを表しています. 一般の \(N,M\) では次の規則で並んでいます.

• まず \(1,2,\dots, M-N-1\) が並ぶ. これらのラベルはすべて A である.
• 次に \(N,M-N,N-1,M-N+1,\dots\) のように並ぶ. ラベルとしては B,A を交互に，番号としては B のラベルは \(N\) から降順に，A のラベルは \(M-N\) から昇順に並ぶ.

ラベルの設定とこの順番には次のような特徴があります.

• A の番号：他の A の番号とペアにできる，先に現れる B の番号とペアにできない，後に現れる B の番号とはペアにできる
• B の番号：他の B の番号とペアにできない，先に現れる A の番号とペアにできる，後に現れる A の番号とはペアにできない

この順番で番号を挿入していくとき，スコアが \(0\) にならないための条件は，

• B の番号は（その時点での）先頭に挿入しない

と表せます. ペアにできない番号の少なくとも一方は B の番号ですが，B の番号を先頭に挿入しないのであれば，先に現れたある A の番号が左にあるので，スコアは \(0\) にはなりません. 逆に，B の番号を先頭に挿入すると，そのようなもののうち最後に挿入した B の番号は，最終的に先頭になってしまうか，後に現れる A のみがいくつか左にあることになりスコアが \(0\) になってしまいます.

次にスコアを与える番号の条件を整理します. まず，

• 挿入した時点で右に B の番号が現れていない

を満たさない番号は，スコアを与えられません. 挿入した時点で右に現れていた B の番号とペアにできないからです. 逆に，この条件を満たす番号のうち最後に挿入した番号がスコアを与えます. まずその番号 \(x\) が実際にスコアを与えること，つまり最終的に手元に \(x\) を残せるということを確認しましょう. \(x\) を挿入してからは，特にその右には挿入されません. 挿入時点では右に B の番号が現れていなかったため，\(x\) が A,B のいずれであったとしても右に現れるすべての番号とペアにできます. 次に，\(x\) より大きな番号はスコアを与えないこと，つまり最終的に手元に \(x\) より大きな番号を残せないということを確認しましょう. \(x\) が B の番号であった場合は簡単です. \(x\) より大きな番号は B の番号に限りますが，B の番号は降順に挿入していて，B の番号のうちスコアを与え得るのは最も右にあるものだけだからです. 一方 \(x\) が A の番号であった場合は少し複雑です. B の番号のうち \(x\) より前に現れている番号は，すべて \(x\) の左に現れていますが，これらは \(x\) とペアにできないためスコアを与えません. A の番号は昇順に挿入しています. したがって A の番号であって \(x\) より大きな番号は \(x\) より後に現れますが，これらはすべて挿入した時点で右に B の番号が現れていることになるので，やはりスコアを与えられません.

ここまでを総合すれば，次のような挿入 DP を設計できます.

\(dp(p,f,x)\coloneqq\)

• \(p\) : すでに現れたある番号がスコアを与えることを確定させたか？
• \(f\) : 挿入途中の \(P\) において先頭から \(2\) 番目の番号は B の番号か？
• \(x\) : 挿入途中の \(P\) において最も右にある B の番号は先頭から \(x\) 番目
• のようなすべての挿入方法に対する，
• \(1\) の総和（方法の個数）（ \(p=0\) のとき）
• スコアの総和 （ \(p=1\) のとき）

とします. ただし，初期値は空列を用いるのではなくて，挿入順で先頭 \(M-N\) 個をすでに挿入した状態から始めるものとしたときの値を用います. こうすることで，B の番号がすでに挿入された状態から始められます. 初期値を設定する際は，スコアを与えることを確定させられるのは唯一の B の番号 \(N\) のみであることに注意してください. スコアを与えることを確定させたあとでは，最も右にある B の番号より左に挿入するように遷移する必要があります. A の番号を挿入するときと B の番号を挿入するときで遷移が変わりますが，詳しい遷移は割愛します. すべての挿入位置を調べる \(O(N^3)\) time の実装例を参考にしてください. この DP は遷移に累積和を用いることで高速化でき，あわせて \(O(N^2)\) time で動作します.

実装例(C++) すべての挿入位置を調べる \(O(N^3)\) time (TLE)

実装例(C++) \(O(N^2)\) time