ARC 201-300/ARC201C - Prefix Covering - 競技プログラミング用 知識集積所

---

問題

ARC201C

必要知識

簡単な内容は省略

• Trie木（未作成）（文字種が2つしかないので、map（未作成）を使わず二分木（未作成）で実装）

考え方

文字列の接頭辞の話なので、Trie木（未作成）の利用を考える。

例えば"AAB"に対応するノードには、

• ちょうどAABで終わる文字列の個数
• AABから始まる任意のAB文字列に対してはよい、AABから始まる文字列だけ考えた部分集合の数
• よいか悪いか関係なく、AABから始まる文字列だけ考えた部分集合の数

を記録しておけばよい。

文字列が追加されたとき、その範囲内ではよい集合は、

• そもそもそこで終わる文字列が含まれる集合
• それにAを足したもの、Bを足したもの、両方にとって範囲内でよい集合ができている場合

の2パターンである。
よってこれを文字列の末尾から遡りながら更新していけばよい。

解答例

解答例

注意点

別解