AtCoder Grand Contest 046 D - Secret Passage

お題箱より。

解法

操作の特徴をつかむ

与えられる文字列 $S$ の長さを $N$ とします。また $S$ の $i$ 文字目を $S_{i}$ と表記します（先頭は $S_{0}$ です）。

操作列によって文字列がどのようになるかを、まずは大雑把に理解しましょう。前から順に操作されるため、元の文字列 $S$ は操作された前側の領域と操作されなかった後ろ側の領域に分かれます。そして操作された文字のうちいくつかが後ろ側に挿入されることによって文字列が完成します。

f:id:betrue12:20201126095848p:plain

削除されなかった文字がどこに挿入されるかは自由です。また、挿入された文字が再び操作の対象となる場合もあり得ます。

このように考えると、操作列の結果としてある状態が作れるかどうかは、その操作列において操作される領域の長さ、後ろに挿入する 0 の個数、後ろに挿入する 1 の個数という3パラメータから判断できることが分かります。例えば上の図の操作であれば $(6, 2, 1)$ です。

これを踏まえて、次のDPを考えましょう。

$E\lbrack i\rbrack\lbrack j\rbrack\lbrack k\rbrack =$ 文字列 $S$ のうち先頭 $i$ 文字を操作することで、0 を $j$ 文字、1 を $k$ 文字後ろ側に挿入することはできるか？（true/false）

初期条件は $E\lbrack 0\rbrack\lbrack 0\rbrack\lbrack 0\rbrack$ がtrueであることです。遷移を考えましょう。 $E\lbrack i\rbrack\lbrack j\rbrack\lbrack k\rbrack$ がtrueであるとき、その状態からの操作を考えることで次に列挙する遷移先をtrueにすることができます。

先頭2文字を操作し、後ろ側の文字をそのままの位置に戻す。実質的に先頭1文字を削った形になり、 $E\lbrack i+1\rbrack\lbrack j\rbrack\lbrack k\rbrack$ がtrueである。
先頭2文字を操作し、そのうちの1文字を後ろに挿入する。 $S_{i}$ と $S_{i+1}$ のうちいずれかが 0 であれば $E\lbrack i+2\rbrack\lbrack j+1\rbrack\lbrack k\rbrack$ がtrueであり、いずれかが 1 であれば $E\lbrack i+2\rbrack\lbrack j\rbrack\lbrack k+1\rbrack$ がtrueである。
これまでの操作で「後ろに挿入する」ということにした文字のうち、 $S_{i}$ と異なる文字を1つ $S_{i}$ の直前に挿入してから、その文字と $S_{i}$ を操作し、 $S_{i}$ を後ろに挿入する。 $S_{i}$ が 0 であれば $E\lbrack i+1\rbrack\lbrack j+1\rbrack\lbrack k-1\rbrack$ がtrueであり、1 であれば $E\lbrack i+1\rbrack\lbrack j-1\rbrack\lbrack k+1\rbrack$ がtrueである。

※遷移1については、厳密には操作されているのは $i+1$ 文字目までではなく $i+2$ 文字目までなのですが…後の説明の都合上、「残っている文字が2文字以上のとき、先頭の文字を1つ削除する」という操作として扱ってしまうことにします。

後で使う性質として、このDPテーブルには単調性が成り立ちます。 $E\lbrack i\rbrack\lbrack j\rbrack\lbrack k\rbrack$ がtrueならば、 $j_{1} \le j$ かつ $k_{1} \le k$ である $(j_{1}, k_{1})$ に対して $E\lbrack i\rbrack\lbrack j_{1}\rbrack\lbrack k_{1}\rbrack$ もtrueです。これは $E\lbrack i\rbrack\lbrack j\rbrack\lbrack k\rbrack$ を実現する遷移列において、遷移2と遷移3を適切に遷移1に置き換えていくことで $j, k$ の値を自由に減らせることから示せます。

このDPテーブルにおいて値がtrueであるような $(i, j, k)$ の組全てについて、

$S$ の後ろ側 $N-i$ 文字に、0 を $j$ 個、1 を $k$ 個挿入してできる文字列が何通りあるか？

を計算して合計すれば答えが求められそうな気がします。しかし、残念ながらこれでは正しい答えになりません。異なる $(i, j, k)$ の組から同じ文字列ができてしまう可能性があるからです。

重複を排除する

操作列によって作ることができる全ての文字列を、それぞれちょうど1回だけ答えに加算する方法を考えます。ある文字列 $T$ が作れるとして、 $T$ を作る時に操作する領域の長さ $i$ をちょうど1通りだけ考えることができれば、操作されない領域に不足している 0 と 1 の個数である $(j, k)$ は一意に定まります。

ここで、次の性質が成り立つことが証明できます。

ある操作列によって文字列 $T$ を作ることが可能であるならば、「 $S$ の接尾辞であって、 $T$ の部分列として取れるもののうち最も長いものの長さ」を $L$ として、 $S$ の末尾 $L$ 文字を操作することなく $T$ を作るような操作列が存在する。

この性質を利用して、 $T$ を作る時に操作する領域の長さを $N-L$ に限定することで、文字列 $T$ をちょうど1回だけ数えることができます。

この性質を証明します。以下の図のように、操作されない領域の長さが $L$ よりも短い操作列Aで $T$ が作れると仮定します。このとき、操作されない領域が1つ長くなるような操作列Bが存在して $T$ が作れることが証明できればよいです。

f:id:betrue12:20201126104925p:plain

直感的には、操作する領域の文字のうち最大で半分しか後ろ側に挿入できないことを考えると、操作する領域の長さが1つ減る代わりに挿入すべき文字が1つ減るのは条件として易しくなってそうな気がします。ちゃんと証明するために冒頭のDPを用います。

操作列Aにおいて操作した領域の長さ、挿入した0の個数、挿入した1の個数を $(i, j, k)$ とします。図のように $S_{i-1}$ が 1 である場合を考えます（ $S_{i-1}$ が 0 である場合も同様に考えられます）。すると操作列Bは $(i-1, j, k-1)$ で特徴づけられるため、「 $E\lbrack i\rbrack\lbrack j\rbrack\lbrack k\rbrack$ がtrueであるならば、 $E\lbrack i-1\rbrack\lbrack j\rbrack\lbrack k-1\rbrack$ もtrueである」ことが証明できれば良いです。

$E\lbrack i\rbrack\lbrack j\rbrack\lbrack k\rbrack$ がtrueであるならば、その遷移元としてあり得る状態のうち少なくとも1つがtrueであるはずです。冒頭の遷移一覧に基づいてこの遷移元を列挙します。

$E\lbrack i-1\rbrack\lbrack j\rbrack\lbrack k\rbrack$
$E\lbrack i-2\rbrack\lbrack j-1\rbrack\lbrack k\rbrack$ （ $S_{i-2}$ が 0 である場合）
$E\lbrack i-2\rbrack\lbrack j\rbrack\lbrack k-1\rbrack$
$E\lbrack i-1\rbrack\lbrack j+1\rbrack\lbrack k-1\rbrack$

第1添字が $i-2$ のものについては、そこから遷移可能な先に置き換えます。すると次のうち少なくとも1つがtrueであることが分かります。

$E\lbrack i-1\rbrack\lbrack j\rbrack\lbrack k\rbrack$
$E\lbrack i-1\rbrack\lbrack j\rbrack\lbrack k-1\rbrack$
$E\lbrack i-1\rbrack\lbrack j+1\rbrack\lbrack k-1\rbrack$

これらは全て、第2添字、第3添字がともに示したい $E\lbrack i-1\rbrack\lbrack j\rbrack\lbrack k-1\rbrack$ の添字以上になっています。よってDPテーブルの単調性から、これらのうちどれがtrueであっても $E\lbrack i-1\rbrack\lbrack j\rbrack\lbrack k-1\rbrack$ がtrueであることが言えます。以上で証明が完了します。

答えを数える

ようやく答えを数えるパートです。これまでの考察から、 $(i, j, k)$ の組全てについて次の値を計算すれば良いです。

$dp\lbrack i\rbrack\lbrack j\rbrack\lbrack k\rbrack$ ： $S$ の後ろ側 $N-i$ 文字に、0 を $j$ 個、1 を $k$ 個挿入してできる文字列であって、「 $S$ の接尾辞であって、 $T$ の部分列として取れるもののうち最も長いものの長さ」が $N-i$ であるものが何通りあるか？

これは文字列 $T$ を後ろから作っていくDPで求めることができます。 $dp\lbrack i\rbrack\lbrack j\rbrack\lbrack k\rbrack$ からの遷移としては、もし $S_{i-1}$ が 0 であれば

文字列の先頭に 0 を付ける：部分列として取れる接尾辞の長さが増えるので、 $dp\lbrack i-1\rbrack\lbrack j\rbrack\lbrack k\rbrack$ に遷移
文字列の先頭に 1 を付ける：部分列として取れる接尾辞の長さが増えず、挿入した文字の扱いになるので、 $dp\lbrack i\rbrack\lbrack j\rbrack\lbrack k+1\rbrack$ に遷移

という2通りの遷移があり得ます。 $S_{i-1}$ が 1 であれば逆です。

$E\lbrack i\rbrack\lbrack j\rbrack\lbrack k\rbrack$ がtrueである $(i, j, k)$ 全てについて $dp\lbrack i\rbrack\lbrack j\rbrack\lbrack k\rbrack$ を合計すれば答えになります。実装によっては空文字列を含んでしまう（ $dp\lbrack N\rbrack\lbrack 0\rbrack\lbrack 0\rbrack$ を算入してしまう）ことがあるので、その場合は $1$ を引きましょう。