https://beta.atcoder.jp/contests/dwacon5th-prelims/tasks/dwacon5th_prelims_c
文字列$S$および$Q$個の整数$k$が与えられる。$S$に"DMC"という部分列（連続でなくてよい）がいくつあるか答えよ。ただし、DとCが$k$文字以上離れていてはならない。
$Q\leq75$個のクエリに答えるので、クエリ1つあたり$O(|S|)$で答えたい。
文字列を前から順に見て、Cが現れたとき、その位置から$k-1$文字前までに存在する"DM"の数を答えに足していけばよい。これをするためには、常に有効な"DM"の数を保持しておけばよくて、これは同様に範囲内のDとMの数を尺取法の要領で持っておくことで簡単にできる（範囲にMが入ってきたらDの数だけ増加し、範囲からDが出て行ったらMの数だけ減少する）。
直感でDPっぽさを感じるのもいいけど、固執しすぎないように。