k-DMC [Dwango Programming Contest V / 第5回 ドワンゴからの挑戦状 予選 C]

https://beta.atcoder.jp/contests/dwacon5th-prelims/tasks/dwacon5th_prelims_c

前提知識

• しゃくとり法

考察過程

1. 制約を見るとO(QN)な感じがする
2. O(N)でアルゴリズムを考えたときに運良くしゃくとり法がしゅっとでた
3. その方針で考えるとAC

解説

https://beta.atcoder.jp/contests/dwacon5th-prelims/submissions/3654309

各クエリをしゃくとり法を使って、O(N)でさばいていこう。
　
c := c-a＜kを満たす最大のc
Mcnt := [a,c]の区間にあるMの個数
Ccnt := [a,c]の区間にあるCの個数
tot := [a,c]の区間にあるM,Cとなるb,cの組み合わせ
これを保持しながら尺取法をする。
aをループしていくのだが、

• S[a]=D : ①cをc-a＜kを満たすまで右に移す（その間、MがあればMcnt++, CがあればCcnt++と、Mcntの個数分totを増やす）②ちょうどtotがS[a]=Dであるときのb,cの全ての組み合わせになっているので、答えに足す
• S[a]=M : Mcnt--, totからCcnt分をへらす（S[b]=Mであるb,cの組を引く）
• S[a]=C : Ccntをへらす

これで答えが出る。

int N; string S; int Q;
//---------------------------------------------------------------------------------------------------
ll solve(int K) {
    ll ans = 0;
    int c = 0;
    int Mcnt = 0;
    int Ccnt = 0;
    ll tot = 0;
    rep(a, 0, N) {
        if (S[a] == 'D') {
            while (c < N and c - a < K) {
                if (S[c] == 'M') Mcnt++;
                else if (S[c] == 'C') {
                    Ccnt++;
                    tot += Mcnt;
                }
                c++;
            }
            ans += tot;
        }
        else if (S[a] == 'M') {
            Mcnt--;
            tot -= Ccnt;
        }
        else if (S[a] == 'C') {
            Ccnt--;
        }
    }
    return ans;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> S >> Q;
    rep(q, 0, Q) {
        int k; cin >> k;
        printf("%lld\n", solve(k));
    }
}