条件を満たす 01 文字列が存在する条件と答えの計算について

\(P_{Q_i}=i\) が成り立つ順列 \(Q\) をとって、 \(Q\) に関する条件と考えます。また、 \(T=S_{P_1}S_{P_2}\dots S_{P_{2N}}\) とします。 \(Q\) の意味合いとしては \(S\) の \(i\) 文字目を 0 にすると \(T\) の \(Q_i\) 文字目が 0 になる、といったものになります。

順列 \(Q\) についての条件は実は以下のようなものと同値です。

• 以下の条件をすべて満たす \(i,j\) が存在しない。
  • \(A_i+A_j=2N\)
  • \((Q_1,Q_2,\dots,Q_{A_i})\) は \((2N-A_i+1,2N-A_i+2,\dots,2N)\) の並べ替えである（\(\iff\) \((Q_{2N-A_j+1.Q_{2N-A_j+2},\dots,Q_{2N}})\) は \((1,2,\dots,A_j)\) の並び替えである）

この事実を前提として数え上げる方法を考えます。 \(A\) の要素のうち \(A_i+A_j=2N\) を満たす \(j\) が存在するようなものを残したうえで、 \(2\) 番目の条件に関して包除原理により計算することを考えます。

包除原理において \(A_{i_1} < A_{i_2} < \dots < A_{i_k}\) に関する条件に違反するものを数えると、 \(A_{i_1}!(A_{i_2}-A_{i_1})!\dots (A_{i_k}-A_{i_{k-1}})!(2N-A_{i_k})!\) 通りとなります。これらについて符号付きの和を計算したいですが、これは \(dp[j] = -\sum dp[i] \times (j-i)!\) という計算を \(dp[A_1],dp[A_2],\dots,dp[A_M],dp[2N]\) に対して行う動的計画法により \(O(N^2)\) で計算できます。さらにこの動的計画法はいわゆる分割統治fftにより高速化できる形になっているため \(O(N\log^2{N})\) 時間で計算できます。

それでは最初に述べた内容を証明しましょう。

必要性

上記のような \(i,j\) が存在するとき、\(P\) についての条件で述べられていた 01 文字列が存在するかについて考えます。まず 01 文字列に関する \(2\) 番目の条件から、 \(S_1,S_2,\dots,S_{A_i}\) のうち \(\frac{A_i+1}{2}\) 文字以上が 0 である必要があります。このことと \(Q\) に関する \(2\) 番目の条件から、 \(T_{2N-A_i+1},T_{2N-A_i+2},\dots,T_{2N}\) のうち \(\frac{A_i+1}{2}\) 文字以上が 0 である必要があることがわかります。つぎに 01 文字列に関する \(3\) 番目の条件から、 \(T_1,T_2,\dots,T_{A_j}\) のうち \(\frac{A_j+1}{2}\) 文字以上が 0 である必要があります。この \(2\) つの条件を考えると \(S_1,S_2,\dots,S_{2N}\) のうち \(\frac{A_i+A_j+2}{2}=N+1\) 文字以上が 0 であることが必要になりますが、これは \(1\) 番目の条件に違反します。

以上より \(Q\) に対し条件を満たす 01 文字列は存在せず、必要性が示せました。

十分性

十分性は以下のような流れで対偶を示すことで証明します。

1. \(S\) が \(2\) 番目の条件を満たす範囲で、 \(i=1,2,\dots,M\) に対して \(T\) の \(A_i\) 文字目までの 0 の個数を同時に最大化するような貪欲アルゴリズムの存在を確認する
2. 固定された \(k\) について、\(S\) が \(2\) 番目の条件を満たす範囲で \(T\) の \(A_k\) 文字目までの 0 の個数を最大化することを考え、これが \(\frac{A_k+1}{2}\) 未満であるとき、最初に述べた条件を満たす \((i,j)\) が存在することを示す

1,2 をあわせて考えると、1 の貪欲アルゴリズムにより構築した \(S\) に対する \(T\) が \(3\) 番目の条件を満たさないとき、最初に述べた条件を満たす \((i,j)\) が存在することが示せます。

1. 貪欲アルゴリズムの存在

条件を満たす \(S\) が存在するかの判定について、以下のような貪欲アルゴリズムを考えます。

貪欲アルゴリズム

1. \(X=\{\}, Y = \{\}\) で初期化する
2. \(i=1,2,...,M\) の順に以下を行う
   • \(X\) に \(Q_{A_{i-1}+1},Q_{A_{i-1}+2},\dots,Q_{A_i}\) を追加する（ただし、 \(A_0=0\) とする）。その後、 \(|Y|=\frac{A_i+1}{2}\) となるまで \(X\) から最小値を pop して \(Y\) に追加することを繰り返す。
3. 最後に \(Q_{A_M+1},Q_{A_M+2},\dots,Q_{2N}\) を追加し、 \(|Y|=N\) となるまで \(X\) から最小値を pop して \(Y\) に追加することを繰り返す。
4. \(i \in Y\) なる \(i\) に対して \(T_i\) が 0 となるように \(S\) を定め、 \(T\) が条件を満たすか判定する

これにより \(S\) が \(2\) 番目の条件を満たす範囲で \(T\) の \(A_i\) 文字目までの 0 の個数が最大化されていることは、 \(2\) 番目の条件について「 \(S\) の \(A_i\) 文字目までの文字のうち、すくなくとも \(\frac{A_i+1}{2}\) 文字が 0 である必要がある。このため、 \(T\) の 0 の位置として、 \(Q_1,Q_2,\dots,Q_{A_i}\) のうち \(\frac{A_i+1}{2}\) 個以上が採用されている必要がある」と考えると明らかです。

2. 固定された \(k\) に対する \(T\) の \(A_k\) 文字目までの 0 の個数の最大値について

\(Q_i \leq A_k\) を満たす \(i\) を \(x_1 < x_2 < \dots < x_n\) とします（ \(n=A_k\) です）。ここで、 \(x_1 \neq 2N-A_k+1\) とすると、ある \(x_1\) より大きい \(2N\) 以下の整数 \(y\) であって、 \(x_2,x_3,\dots,x_n\) のいずれでもないものが存在します。このとき、

1. \(S=\) ??...? から始める。 \(S\) の \(x_1\) 文字目を 0 とし、 \(y\) 文字目を 1 とする
2. \(i=2,4,\dots,n-1\) に対し、 \(S\) の \(x_i\) 文字目を 0 とし、 \(x_{i+1}\) 文字目を 1 とする
3. \(S\) のまだ 0,1 のどちらか決まっていない \(2N-n-1\) 文字について、0,1 を交互に配置する

という手順で \(S\) を構築してみます。すると構築過程において、 \(S\) の任意のprefixにおいて（ 0 の数）\(-\) （1の数）は変化しないか \(1\) だけ増えているので、構築された \(S\) は任意の prefix において 0 の数が 1 の数以上になっており、 \(2\) 番目の条件を必ず満たします。また、 \(T\) の \(A_k\) 文字目までの 0 の数は \(\frac{A_k+1}{2}\) 個となっています。このことから \(S\) が \(2\) 番目の条件を満たす範囲での \(T\) の \(A_k\) 文字目までの 0 の個数の最大値が \(\frac{A_k+1}{2}\) 未満であるには \(x_i=2N-A_k+i\) であること、すなわち \((Q_{2N-A_k+1},Q_{2N-A_k+2},\dots,Q_{2N})\) は \((1,2,\dots,A_k)\) の並び替えになっていることが必要です。

この条件の下で、つぎに以下のような手順で構成された \(S\) について考えます。

1. \(S\) の \(2N-A_k\) 文字目を 1 とし、 \(2N-A_k+1\) 文字目を 0 とする
2. \(i=2,4,\dots,n-1\) に対し、 \(S\) の \(2N-A_k+i\) 文字目を 0 とし、 \(2N-A_k+i+1\) 文字目を 1 とする
3. \(S\) の先頭 \(2N-n-1\) 文字について 0,1 を交互に配置する

このとき \(S\) は 0101...01 という文字列で \(2N-A_k,2N-A_k+1\) 文字目をswapしたものになっており、 prefix において 0 の数が 1 の数がすくなくなるのは先頭 \(2N-A_k\) 文字に着目したときだけです。このため、 \(A_{k'}=2N-A_k\) をみたす \(k'\) が存在しないとき、 \(S\) は \(2\) 番目の条件を満たします。また、 \(T\) の \(A_k\) 文字目までの 0 の個数は \(\frac{A_i+1}{2}\) 個となっています。このことから \(S\) が \(2\) 番目の条件を満たす範囲での \(T\) の \(A_k\) 文字目までの 0 の個数の最大値が \(\frac{A_k+1}{2}\) 未満であるには \(2N-A_k=A_{k'}\) を満たす \(k'\) が存在することも必要です。

以上をまとめると、 \(S\) が \(2\) 番目の条件を満たす範囲での \(T\) の \(A_k\) 文字目までの 0 の個数の最大値が \(\frac{A_k+1}{2}\) 未満であるには

• \((Q_{2N-A_k+1},Q_{2N-A_k+2},\dots,Q_{2N})\) は \((1,2,\dots,A_k)\) の並び替えになっていること
• \(2N-A_k=A_{k'}\) を満たす \(k'\) が存在すること

が必要であり、このとき冒頭で述べた条件を満たす \((i,j)\) として \((i,j)=(k',k)\) がとれます。以上より示されました。