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

終了46秒前に通ってアツかった。

問題

解法

dpがちらついたが，順番に並んでいる3つ組を数えるときは，中央を固定するのが定石なので，とりあえずそれに従って考えてみる。ここで，もし $c-a\lt k$ という条件がなければ，これは単に $S$ に現れる「DMCという部分列の数」を数えるだけである。つまり，'D','M','C'の出現数について累積和を取っておき，各'M'について「その'M'より左にある'D'の数」と「その'M'より右にある'C'の数」の積を取ればよい。
さらに，「 $c-a\geqq k$ をみたすDMCという部分列の数」がわかれば，これを「DMCという部分列の数」から引くことで答えが求まる。ここが1つのポイントだろう。

それでは，「 $c-a\geqq k$ をみたすDMCという部分列の数」を求めよう。'D'の位置を $a$ ，'M'の位置を $b$ ，'C'の位置を $c$ とする。DMCという部分列であって，この条件を満たすとき， $a,b,c$ の関係として考えられるものは

$b\lt a+k$ かつ $a+k \leqq c$ ('C'だけ遠い)
$a+k \leqq b \lt c$ ('M'も'C'も遠い)

の2つであり，これらは排反である。1の方は，区間 $[a+1,a+k)$ にある'M'の数と， $[a+k,N$ ]にある'C'の数が求まればよいから，'M'と'C'の累積和を使えば $O(1)$ で求まる(詳細は提出参照)。2の方は，「位置 $i$ より右にあるMCという部分列の数」を事前に求めておけば $O(1)$ で求まる(これも累積和，提出参照)。よって，各 $k$ の値に対して $O(N)$ で答えが求まるので，全体として $O(QN)$ であり，十分高速である。