ABC 401-500/ABC452D - No-Subsequence Substring - 競技プログラミング用 知識集積所

---

問題

ABC452D

必要知識

B以下レベルの内容は省略

• 動的計画法

考え方

全部見ていては、当然O(|S|^2*|T|)でTLE。
どうにかO(|S|*|T|)まで下げられれば間に合うので、Sの部分文字列の終了位置ごとに高速に処理したいと考える。

そこで、データを「その文字で終わる部分文字列のうち、Tの先頭から何個目までを部分列にもつか」の個数で持つ。
例えば入力例1の5文字目のkについては、"abrak","brak","rak","ak","k"がそれぞれ"aba"の何文字目まで持っているか考えて、{1,3,0}というデータで持つ。
（最初の1が"k"の分、次の3が"brak","rak","ak"の分。"abrak"はTを完走していて条件に当てはまらない）

これをテーブルとして継承しながら、終了位置を1つずつずらす動的計画法を行えばよい。
すなわち、新しい終了位置の文字が例えば'a'であるなら、

• Tを'a'の直前まで含んでいたものが、もう1文字長く部分列をもつようになる
• そこが開始位置になる文字列の処理用に、空文字列相当として長さ0のところを1個追加する

を更新処理とすればよい。

答えは各段階でのデータ全体の数値の総和の総和。
更新処理と並行で集計していくとよい。
面倒なのは、空文字列のカウント処理。
「空文字列以外の」という指定があるので、誤ってカウントしてはいけない。
最初からデータに入らないように工夫するか、最後にまとめて空文字列分を引くかする。

解答例

解答例

注意点

long long※型を用いる

ほぼ全部分文字列が条件を満たす場合、およそ(1/2)N^2個くらいが答えになり、int型には収まらない。

別解