O - 0100 Insertion Editorial
by 
milkcoffee
0,1 からなる文字列 \(S\) が 良い文字列 かどうかの判定問題を考えます。
以下では、文字列 \(S\) を逆順に並べ替えた上で、 0100 の挿入ではなく 0010 の挿入を行う問題を考えます。(答えは変わりません)
明らかに、\(S\) に 0,1 が \(3:1\) の比で存在している必要があります。
また、挿入によって 1 が連続することはないため、 \(S\) に 1 が連続する部分が存在してはなりません。1 は先頭や末尾になることもないため、 \(S\) の先頭と末尾に 1 が存在してはいけません。
これらの条件を満たした上で、\(S\) が 良い文字列 となる必要十分条件は以下のようになります。(証明後述)
0を \(+1\) に置き換え,1を \(-3\) に置き換えた長さ \(N\) の数列 \((A_1,A_2,...,A_N)\) を作る。- \(A\) の左からの累積和を \((B_0,B_1,...,B_N)\) とする。ただし、 \(B_0 = 0\) とする。
- \(B\) の左からの累積 min を \((C_0,C_1,...,C_N)\) とする。ただし、 \(C_0=0\) とする。
- 任意の \(i \ (0 \leq i \leq N-1)\) において、 \(C_{i+1} =C_{i}\) または \(C_{i+1} = C_{i} - 1\) が成り立つ。
例えば \(S=\) 00100100 のとき、
\(A=(1,1,-3,1,1,-3,1,1)\)
\(B=(0,1,2,-1,0,1,-2,-1,0)\)
\(C=(0,0,0,-1,-1,-1,-2,-2,-2)\)
これは 良い文字列 です。
また、 \(S=\) 00101000 のとき、
\(A=(1,1,-3,1,-3,1,1,1)\)
\(B=(0,1,2,-1,0,-3,-2,-1,0)\)
\(C=(0,0,0,-1,-1,-3,-3,-3,-3)\)
これは 良い文字列 ではありません (\(C_5 = C_4 -2\) であるため) 。
証明
まず、操作によって作れる文字列はこの条件を満たします。 なぜなら、挿入した場所より後ろの部分の累積和は変わらず、挿入した部分についても累積 min は 直前の値 $-1$ より小さくはならないからです。逆に、上の条件を満たす文字列が操作によって得られることを示します。
条件を満たす文字列 $S$ から
0010 を取り除く操作 を繰り返して空文字列にできることを示せればよいです。 $S$ に対応する $B_i$ で、$B_{i-1} > B_i < B_{i+1}$ となっている $B_i$ を極小部と呼ぶことにします。ここで、先頭の $B_0$ も極小部に含めることにします。
ある極小部 $B_x$ とその次の極小部 $B_y$ で $B_x \leq B_y$ となっているものを考えます。このとき、$x,y$ の間には $3$ つ以上の
0 が連続しているため、 $S_{y-3}S_{y-2}S_{y-1}$ はいずれも 0 です。また、$S_y=$1 ということに注意すると、1 は連続しないという条件より $S_{y+1}=$ 0 です。そのため、0010 を取り除く操作として、 $S_{y-2}S_{y-1}S_yS_{y+1}$ を取り除くことができます。ここで、$S_{y-3}=$
0 であるため取り除いた後に 1 が連続することはなく、残された部分の累積和と累積minも変わらないため、取り除いた後の文字列も条件を満たします。この操作を繰り返すと任意の極小部 $B_x$ とその次の極小部 $B_y$ で $B_x > B_y$ が成り立つようになります。ここで、$S$ が $C$ の条件を満たしていることに注意すれば、$B_y = B_x-1$ となっていることが分かります。
これに対応する文字列は
001 を $k$ 回繰り返した後に 0 を $k$ 回繰り返したような文字列になっています。この文字列に対しては最後の 1 から取り除いていくような操作を $k$ 回行うことにより、空文字列にすることができます。
これにより判定問題が解けました。
数え上げは以下のような DP で行うことができます。
\(\text{dp}[i][j][k][l]:=\) \(S\) の \(i\) 番目の文字まで見て、\(B_i = j\) かつ \(C_i=k\) かつ最後の文字が \(l (0 \ \text{or} \ 1)\) であるものの個数
計算量は \(O(N^3)\) です。
posted:
last update: