AtCoder Beginner Contest 301 F - Anti-DDoS
メモ
以下ではDDoS文字を数える
まず判定問題を考えて問題を簡潔にしたい。
これは排反に数え上げる上でも役立つ。
ある文字列にDDoS文字が含まれていても、その文字列を複数回数えないようにしたい。
こういうものはよく、最初に現れる何かの位置が最小になるように決めるなどの
貪欲的な手法がとられる
今回は文字列SにDDoSが含まれる際に、DDoSのoの部分が一番右になるようなものについて数えることにする
oの位置を順に右から見ていき
oSとなるものの場合の数を求め
また、oより左に同じ大文字が現れる場合の数を求めればいい
公式の解法は、確率的に状態をもちながら行う耳dpだったようだ
ここで重要なのは大文字としてあらわれているものの情報は、今までに何種類現れたかというものだけで充分であるという点
