入力の \(B\) はソートされているものとします．

Max Bracket Score を問題 X とします． \((2N)!\) 通りの並び替えすべてに対する問題 X の答えの総和はある整数列 \(K\) を用いて \(\displaystyle\sum_{i=1}^{2N}K_iB_i\) と表すことができます． \(K\) を求めることが目標です．

問題を少しいいかえる

問題 X の問題文における括弧列 \(s\) のスコアを次のように変えた問題を考えることにします．

• \(s_i\) が ( なら \(d_i=1\)，) なら \(d_i=-1\) として， \(\displaystyle\sum_{i=1}^{2N}d_iA_i\)

これを問題 X’ と呼ぶことにします． \((2N)!\) 通りの並び替えすべてに対する問題 X’ の答えの総和は \(\displaystyle\sum_{i=1}^{2N}(2K_i-(2N)!)B_i\) になります． \(K'_i=2K_i-(2N)!\) とします．

問題 X’ は以下の手順で求めることができます．

• \(\mathrm{score}=A_1-A_{2N}\) とし，空の優先度付きキュー \(Q\) を用意する．
• \(i=1,2,\ldots,N-1\) に対して以下の操作を行う
  • \(Q\) に \(A_{2i},A_{2i+1}\) を追加する
  • \(Q\) から最大値を取り出し， \(\mathrm{score}\) にその値を加える．
• \(Q\) に残った要素の総和を \(\mathrm{score}\) から引く．
• 最終的な \(\mathrm{score}\) が答え．

int score = A[1] - A[2 * N];
priority_queue<int> Q;
for (int i = 1; i < N; i++){
  Q.push(A[2 * i]);
  Q.push(A[2 * i + 1]);
  score += Q.top();
  Q.pop();
}
while (!Q.empty()){
  score -= Q.top();
  Q.pop();
}
cout << score << endl;

問題 X’ では必ず A[1] - A[2 * N] は score に含まれるため，あらかじめこれを除いて考えることにします．以下の問題を問題 Y とします．

• 長さ \(2n(=2(N-1))\) の数列 \(a\) が与えられる．
• \(\mathrm{score}=0\) とし，空の優先度付きキュー \(Q\) を用意する．
• \(i=1,2,\ldots,n(=N-1)\) に対して以下の操作を行う
  • \(Q\) に \(a_{2i-1},a_{2i}\) を追加する
  • \(Q\) から最大値を取り出し， \(\mathrm{score}\) にその値を加える．
• \(Q\) に残った要素の総和を \(\mathrm{score}\) から引く．
• 最終的な \(\mathrm{score}\) を求めよ．

int score = 0;
priority_queue<int> Q;
for (int i = 1; i < n; i++){
  Q.push(a[2 * i - 1]);
  Q.push(a[2 * i]);
  score += Q.top();
  Q.pop();
}
while (!Q.empty()){
  score -= Q.top();
  Q.pop();
}
cout << score << endl;

\(a\) の \((2n)!\) すべての並び替えに対する問題 Y の答えの総和はある整数列 \(L\) を用いて \(\displaystyle\sum_{i=1}^{2N}L_ia_i\) と表すことができます．

ここで，数列 \(K'\) と \(L\) には以下の関係が成り立ちます．（問題 X’ において \(A[1],A[2N]\) と残りの数の大小関係について注目すると良いです）．

• \(K'_i=(2N-1)!+L_i\times2\dbinom{2N-1-i}{2}+L_{i-1}\times 2i(2N-1-i)+L_{i-2}\times 2\dbinom{i}{2}\)

以降では \(L\) を導出します．

寄与を差分として考える

次の値を \(d(c_1)\) とします．

• \(0\) を \(2n-c_1\) 個， \(1\) を \(c_1\) 個含むようなすべての数列に対する問題 Y の総和に \(c_1!(2N-c_1)!\) を乗じた値

このとき，差分を考えることにより \(L_i=f(i)-f(i-1)\) が成り立ちます．よって \(f(0),f(1),\ldots,f(2n)\) が分かればよいです．

01 列に対する 問題 Y の解法

一般の数列の場合には優先度付きキューを用いていましたが，01 の場合では単に \(1\) の個数を管理するだけでよくなります．見通しをよくするために， \(1\) の場所を stack で管理し，適宜末尾で出し入れすることを考えます．（このように取り出す \(1\) に条件を付けることでダブルカウンティングを避けています．）

\(01\) 列を \(b\) とします．このとき， \(b_i\) が 1 であるような各 \(i(1\leq i\leq 2n)\) に対して，どのタイミングでその \(i\) が stack から取り出されるかを考えることにします． \(b_i=1\) なら \(t_i=\) (， \(b_i=0\) なら \(t_i=\) ) となるかっこ列を \(s_b\) とします．

1. \(b_{2i-1},b_{2i}\) の片方が \(0\) で片方が \(1\) の場合
   この場合，即座に その \(1\) が取り出されます．スコアへの寄与は \(+1\) です．

2. \(b_{2i-1},b_{2i}\) がともに \(1\) のとき
   この場合， \(b_{2i-1}\) の \(1\) は即座に取り出されます． \(b_{2i}\) は最後まで取り出されるかどうかわかりませんが，取り出されるときは \(s_b[2i-1:2j]\) が正しい括弧列となるような最小の \(j\) に対応する場所で取り出されることが分かります．
   ここで， \(b_{2i}\) が取り出されなかった場合を考えましょう．このとき最終的にその分が \(-1\) として答えに寄与しますが，これは \(b_{2i}\) の \(+1\) の寄与の分と打ち消し合うと考えることができます．
   したがって， \(s_b[2i-1:2j]\) が正しい括弧列となるような場合にのみ答えに \(+2\) が寄与すると考えることができます．

以上をまとめると， \(b\) のスコアへの寄与は次のようにみなすことができます．

1. \(s_b[2i-1:2i]\) が () のとき \(+1\)
2. \(s_b[2i-1:2i]\) が )( のとき \(+1\)
3. \(s_b[2i-1:2j]\ (i\lt j)\) が ( + （正しい括弧列）+ ) のとき \(+2\)

FPS の合成の利用

\(1\) の個数が \(i\) であるような 01 列すべてに対する問題 Y の答えの総和を \(g_i\) とし， \(g_i\) の母関数を \(g\) とします．上の 3 つをまとめると

\[ g=\sum _{d=1}^n 2C_{d-1}(n-d+1) x^d(1+x)^{2(n-d)}=(1+x)^{2n}\sum_{d=1}^n 2C_{d-1}(n-d+1) \left(\dfrac{x}{(1+x)^2}\right)^d\]

です．ここで， \(C_d\) はカタラン数です．この \(g\) は形式的冪級数の合成を用いることで \(O(N\log ^2N)\) で求めることができます． 後は \(f(i)=i!(2n-i)!g_i\) により \(f\) が求まるので \(L,K',K\) がそれぞれ求められ答えが求まります．

合成を使わずに \(O(N\log N)\) で解いたり，別の導出によって \(O(N)\) で解くことも可能です．（ユーザー解説）