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

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

解法

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