第5回　ドワンゴからの挑戦状予選 - C - k-DMC - Senの競技プログラミング備忘録

長さNの文字列Sが与えられる。Q回の質問ごとに与えられるkについて、次の条件を満たすような(a, b, c)のセットの数を答えよ。

制約：　1 <= Q <= 75, 3 <= N <= 10^6, 3 <= k <= N

1. O(NQ)なら間に合いそう。O(N)で数え上げられると嬉しいなぁ。
2. 最後の制約は先頭と後尾にのみ依存。何かしらを固定するのなら先頭or後尾固定がやりやすそう。
3. 先頭を固定して考えてみる。差分をうまく更新していけるパターンだと気付く！
4. AC

先頭を固定して、いい感じに差分で何個あるのか？ができればうれしい。(上のACするまでのように考えると)
先頭を固定して考えるので、実質的に組み合わせを考える必要があるのは、'M'と'C'だけである。

先頭が'D'として、c-a

i
S[i]=='M'ならば、countMを1増やす。
S[i]=='C'ならば、countCを1増やし、「答え増分」に今の時点のcountMだけ加算する。(先頭がDと仮定すると、今あるCを後尾としたときに、Mの候補はcountMだけあるため)

そして、先頭を増やすたびに、(先頭が'D'なら)答えに「答え増分」の値を足せばよい。(答え増分は、先頭が'D'と仮定した時のペアの数なので)

さて、いかにして差分を更新していくのだろうか？
先頭の場所を進める前に、差分更新処理をする。(しゃくとり法のように実装した。しゃくとり法のテンプレは以下を参照)

実質的に考えるのは(b, c)のペアである。(先頭は決め打ちするイメージ)

S[i]=='D'の場合は、なにもしなくてよい。(ansに現時点の答え増分を足すだけ)
S[i]=='M'は、その時点で作れなくなる(b, c)のペアは、そのMにはその'M'を使い、Cには現時点で使えるすべての'C'(countC個)を使ったペアである。(Mが最左端にあるので、使えるすべての'C'とペアを作れる)そして、countMを1減らす。
S[i]=='C'は、その時点での作れなくなる(b, c)のペアはないので(左から一番目が'C'なら、その文字を始点としてMCを構築することはない。)、単純にcountCを1減らす。

これは、最初に求めたcountM, countCを加算などと同じような処理をすればよい。

このようにleftやrightを処理すると、左端を1つ減らして右端を1つ増やした時に変動する(先頭を'D'としたときの)ペアの数をO(1)で、差分更新できる。

実際の実装はしゃくとり法で行った。

これがこのブログの100記事目。