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

問題概要

'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;
        }
    }
}

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

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

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

問題概要

制約

考えたこと

各クエリ

区間の右側を進める

区間の左側を進める