Substrings [AtCoder Beginner Contest 214 F]

https://atcoder.jp/contests/abc214/tasks/abc214_f

前提知識

• 動的計画法

解説

https://atcoder.jp/contests/abc214/submissions/25062984

今回の問題は部分列DPを見たことが無いと難しいかもしれない。
こちらを理解しておくことで、今回の問題をスムーズに理解できる。

部分列DP

部分列DPについては、
部分列 DP --- 文字列の部分文字列を重複なく走査する DP の特集 - Qiita
が最も細かい。
補足であるが、この部分列DPについてはDEGwerさん資料でgreedyからの帰着にて触れられており、
それ以外にも多数の重要典型がまとめられているので、必見である。
「数え上げテクニック集」を公開しました
DEGwerさんの数え上げテクニック集問題まとめ - はまやんはまやんはまやん

さて、以降部分列DPについては理解できているものとして話を進める。
真面目に部分列DPを説明してもいいのだが、先人の記事を参照する方が恐らくwin-winだ。
この問題は部分列DPの2番目の問題として最適である。1番目の問題として取り込んでも、それなりに問題ない。

今回の問題

クエリを見直してみよう。
基本的には印がついている場合だけ文字を残してできる部分列を同じ文字については
同一視して数え上げるというのが要求事項となる。
これはまさに部分列DPの典型問題として取り上げられているものである。
違いは選択できる文字が連続してはいけないということになる。

今回のアルゴリズム

ベースは部分列DPと同様である。

dp[i][lst] := i文字目までの文字を使って最後がlstであるような文字列の組み合わせ
として、文字列選択をする場合は、「貪欲に」先頭から文字を使う場所を選択することにする。

これだと全く同じなのだが、遷移時にもう一つ条件を付け加えることにする。
貪欲に文字を選択した場合に隣の文字になってしまったら、もう一度貪欲に文字を選択して遷移先を決める。
つまり、

baa  
^  

と、bを選択している状態の場合、次の文字としてaを使うことを決めて、貪欲に遷移すると、
1つ隣となるが、これだと条件を満たさなくなるので、もう一度同じ文字aで貪欲に遷移させて、

baa  
  ^  

のように遷移させることにする。
このように必要なら更に遷移させることで、貪欲に選択して、かつ、隣でない要素を素早く見つけることができる。

実装

部分列DPの実装で厄介な所が、文字列について次にとある文字が来る場所を見つける部分である。
自分はこの辺は昔に実装してStringMasterとしてまとめている、今回貼ったのはその一部である。

sm.getNext(idx, char) := 文字列のidx番目以降で最初に文字charがある添え字

dpというか累積和的な感じというかで配列を準備して、O(1)で以上の関数が答えられるようにする。

string S;
int N;
mint dp[201010][26];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S;

    StringMaster sm(S);
    N = S.length();

    rep(nxt, 0, 26) dp[sm.getNext(0, char('a' + nxt))][nxt] = 1;
    rep(i, 0, N) rep(lst, 0, 26) rep(nxt, 0, 26) {
        int i2 = sm.getNext(i + 1, char('a' + nxt));
        if (i + 1 == i2) i2 = sm.getNext(i2 + 1, char('a' + nxt));
        dp[i2][nxt] += dp[i][lst];
    }

    mint ans = 0;
    rep(i, 0, N) rep(lst, 0, 26) ans += dp[i][lst];
    cout << ans << endl;
}