Codeforces Round #501 (Div. 3) F. Bracket Substring

お題箱より。

Problem - F - Codeforces

問題概要

整数 $n$ と、開き括弧・閉じ括弧からなる文字列 $s$ が与えられる。長さ $2n$ の正しい括弧列であって、その連続部分文字列として $s$ をどこかに含むものの個数を $\bmod 10^{9}+7$ で求めよ。

制約

$1 \le n \le 100$
$1 \le |s| \le 200$

解法

DPを立てる

正しい括弧列の問題は、( を $+1$ 、) を $-1$ とした累積和を考えるのが定石です。先頭からの累積和がどの時点でも負にならず、かつ最後に $0$ になるものが正しい括弧列です。

今回のように制約が小さく、「数学で一発」みたいな解法が考えづらい場合、以下のようなDPを考えることが多いです。

$dp\lbrack i \rbrack\lbrack j \rbrack\lbrack ? \rbrack =$ 先頭 $i$ 文字までを作って、その時点までの累積和が $j$ で、かつ○○が $?$ であるものの個数。

正しい括弧列の条件を守るため、 $j$ が負のところには遷移しないようにして、最終的に $j=0$ のものだけを答えとして採用します。

$?$ の部分に問題特有の条件が入ってきます。今回の問題の場合は「連続部分文字列として $s$ をどこかに含むもの」なので、追加で必要な状態をこのように設定します。

$dp\lbrack i \rbrack\lbrack j \rbrack\lbrack k \rbrack\lbrack f \rbrack =$ 先頭 $i$ 文字までを作って、その時点までの累積和が $j$ で、かつ直近 $k$ 文字が $s$ の先頭 $k$ 文字と一致していて、かつこれまでの文字列の中に既に $s$ が含まれている（ $f=1$ ）/いない（ $f=0$ ）ものの個数。

※より厳密に書くと、「『直近 $x$ 文字が $s$ の先頭 $x$ 文字と一致している』という条件を満たす最大の $x$ が $k$ である」のほうが正しいです。例えば $s$ が ()() の場合、()( は $k=0,1,3$ に対して先ほどのことが成り立ちますが、マッチするもののうち最も長いものを取って $k=3$ にだけ算入します。

添字が2個増えました。まず $k$ については「今どこまで $s$ にマッチしているか」を表します。そして $f$ は言わば「クリア済みフラグ」で、1度でも $s$ が完成したら $f=1$ にして遷移します。こうすれば最後に、正しい括弧列かつ1度以上 $s$ が登場するものを数えることができます。

各遷移では開き括弧と閉じ括弧の両方を試します。このとき $s$ が $k$ 文字まで一致しているので、その続きとして正解のほうの文字であれば $k+1$ に遷移すれば良いですが、異なるほうの文字だったらどうすれば良いでしょう？これは単に「全部やり直し」で $k=0$ に遷移するわけではなく、もう少し考える必要があります。

$k$ の遷移を考える

具体例を示します。 $s$ が ()(() だったとしましょう。これまで作った文字列が ()( であったとき、これは累積和が $+1$ で直近 $3$ 文字が $s$ の先頭と一致しているので状態としては $dp\lbrack 3 \rbrack\lbrack 1 \rbrack\lbrack 3 \rbrack\lbrack 0 \rbrack$ に属しています。

ここで ( を付けて ()(( とすると、これは $s$ の続きとして「正解」なので $k$ が1つ増えて $dp\lbrack 4 \rbrack\lbrack 2 \rbrack\lbrack 4 \rbrack\lbrack 0 \rbrack$ に遷移します。

一方 ) を付けて ()() とした場合、今まで続けてきた $s$ は途切れます。ですが改めて見ると直近 $2$ 文字について $s$ の先頭と一致しています。つまりこの場合 $dp\lbrack 4 \rbrack\lbrack 0 \rbrack\lbrack 2 \rbrack\lbrack 0 \rbrack$ に遷移する必要があります。

この遷移を実現するために必要なのは、「 $s$ の先頭 $k$ 文字が完成している状態で、この文字を付け加えると、その後は最大何文字マッチしている状態になるか？」という値を前計算することです。正解のほうは $k+1$ になりますし、そうでないほうは実際に試してみることになります。 $O(n^{3})$ 掛けて良いので地道に全部試してOKです。