Processing math: 0%

$\def\bra#1{\mathinner{\left\langle{#1}\right|}} \def\ket#1{\mathinner{\left|{#1}\right\rangle}} \def\braket#1#2{\mathinner{\left\langle{#1}\middle|#2\right\rangle}}$

◇◇ref017:Dwango Programming Contest V - C : k-DMC◇◇

☆問題URL

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っぽさを感じるのもいいけど、固執しすぎないように。

戻る