けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

第5回 ドワンゴからの挑戦状 予選 2018 C - k-DMC (600 点)

差分更新系の代表的問題。でも頭がごっちゃになって大変だった。

問題へのリンク

問題概要

'D', 'M', 'C' からなる長さ  N の文字列  S と正の整数  K が与えられる。 S の添字  a \lt b \lt c であって

  • S[  a ] = 'D'
  • S[  b ] = 'M'
  • S[  c ] = 'C'
  •  c - a \lt K

を満たすものの個数を求めよ (というクエリに  Q (\le 75) 回答えよ...各クエリは  K が指定される)。

制約

  •  3 \le N \le 10^{6}
  •  1 \le Q \le 75

考えたこと

一瞬、苦手なクエリ処理系かと思ったけど、 Q \le 75 というのを見た時点で、なんか変な高速化解法を封じるためなのかな...となった。あまりクエリ形式は本質でなさそうと。であれば問題ない!!!

で、各クエリに  O(N) で答えられれば問題ない!!!僕の苦手なクエリ系は、最初は  O(N) で前処理してもいいけどその後は  O(1) O(\log{N}) が要求されるようなやつ。今回のはそうじゃない。

各クエリ

というわけなので、実質  N, K が与えられて  O(N) な線形処理を目指す問題として解くことにする。こういう  a, b, c と添字が 3 つあるタイプの問題では、真ん中を固定するのが定石なのだが...今回はそれだと  c - a \lt K という条件と相性が悪いので、今回は、とりあえず  D の位置  a を固定して考える。

そうしたときに  b, c として満たすものは

  •  c - a \lt K を満たすような各  c (S[  c ] = 'C') に対して
  •  a c の間に挟まっている 'M' の個数を合計したもの

になることがわかる。この値は、差分更新によって求められそうである。一般に、

区間 [tex: l, r) について

  • 'M' の個数 ( m)
  • 'C' の個数 ( c)
  • 'M', 'C' のこの順になっているペアの個数 ( t)

を管理することにする。よくある定石として

  • 区間の右側を進めるときの変化
  • 区間の左側を進めるときの変化

を考えて更新する、を考えるとわかりやすい。

区間の右側を進める

進めたことで追加される文字 c を考える

  • c = 'M' のとき、++m
  • c = 'C' のとき、++c, t += m

区間の左側を進める

進めたことで削除される文字 c を考える

  • c = 'M' のとき、--m, t -= c
  • c = 'C' のとき、--c
#include <iostream>
#include <string>
using namespace std;

int N;
string S;
long long m, c, t;

void add(int i) {
    if (S[i] == 'M') ++m;
    else if (S[i] == 'C') ++c, t += m;
}

void erase(int i) {
    if (S[i] == 'M') --m, t -= c;
    else if (S[i] == 'C') --c;
}

long long solve(int K) {
    long long res = 0;
    m = 0; t = 0;
    int r = 0;
    for (int l = 0; l < N;) {
        while (r < N && r - l < K) add(r++);
        if (S[l] == 'D') res += t;
        erase(l++);
    }
    return res;
}

int main() {
    while (cin >> N >> S) {
        int Q; cin >> Q;
        for (int i = 0; i < Q; ++i) {
            int k; cin >> k;
            cout << solve(k) << endl;
        }
    }
}