第5回 ドワンゴからの挑戦状 予選 C - k-DMC

問題
提出コード
WAしていたコードの冗長な部分をコンパクトに書き直していたら、バグが消えていたのに提出しなかったので、結局時間内にACすることができませんでした…パフォが400ほど変わるのでめちゃくちゃ悔しいです。知らぬ間にバグが消えていたパターンの対処法、募集します。

解法

まずは真ん中、つまりに注目しますが、うまくいきそうになかったので今度はに注目します。
を使う場所を決めたときにできる、との組み合わせの個数が求まれば、この問題を解くことができます。
前から見ていったときに、今見ている文字がだったら、その時点で使用できるの個数を追加し、文字前がだったら、それ以降はそのを使用できなくなるので、文字の区間にあるの個数を引きます。こうすることで、ある場所にいる際にできるとの組み合わせの数がわかります。なので、が見つかったら、その時点で使用できる組み合わせの数を追加していけば、答えが求まります。
ある区間に対するとの個数が知りたいので、累積和を使えばで求めることができます。

• のとき
  までのの個数からまでのの個数を引いたものを足します。

• のとき
  今使用できる組み合わせを答えに加算します。

• のとき
  までのの個数からまでのの個数をひいたものを引けばよいです。

これを繰り返せば、答えを求めることができます。