【AtCoder】ABC 441 E - A > B substring

2026-01-24

AtCoder/ABC/E問題 AtCoder/ABC/450点問題 AtCoder/緑Diff AtCoder/NoviSteps/1D AtCoder/データ構造/BIT(Fenwick Tree)AtCoder/累積和 AtCoder/文字列探索/連続部分文字列競技プログラミング

E - A > B substring

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoder

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 969 / NoviSteps: 1D / 配点: 450 点

問題概要

A,B,Cの $3$ 種類の文字からなる長さ $N$ の文字列 $S$ が与えられる。

$S$ の空でない連続部分文字列であって、AがBよりも多く含まれるものはいくつあるか求めよ。ただし、 $2$ つの部分文字列は、 $S$ から取り出す場所が異なれば文字列として等しくても区別して数えることに注意すること。

制約

$1\le N \le 5 \times 10 ^ 5$
$N$ は整数

考察

文字のままだと考えにくいので、Aを $+1$ 、Bを $-1$ 、Cを $0$ として数列 $A$ に変換する。

すると、 $S$ の $l$ 文字目から $r$ 文字目までの連続部分文字列においてAの数がBの数より多くなるのは、 $\displaystyle \sum_{i=l}^{r} A_i > 0$ となるときである。

さらに、数列 $A$ の累積和を $P_j = \displaystyle \sum_{i=1}^{j} A_i \quad (P_0 = 0)$ とすると、条件は $P_r - P_{l-1} > 0 \iff P_r > P_{l-1}$ となる。したがって、この問題は

$0 \leq i < j \leq N$ を満たす組 $(i, j)$ の個数であって、 $P_j > P_i$ を満たすものを求めよ。

という問題に帰着できる。

これは転倒数を数える要領で、 $P$ の各要素を左から順に見ていき、今見ている要素より小さい要素の個数を数え上げればよい。

BIT (Fenwick Tree) を用いると、各要素の個数の更新と自身より小さい要素の個数の取得をそれぞれ $O(\log N)$ 時間で行えるため、全体で $O(N \log N)$ の計算量で解くことができる。

実装例

ACLのfenwick_treeを用いると簡潔に書くことができるのでオススメ。

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#if __has_include(<atcoder/all>)
5.#include <atcoder/all>
6.using namespace atcoder;
7.#endif
8. 
9.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
10. 
11.using ll = long long;
12. 
13.// ======================================== //
14. 
15.int main()
16.{
17.    int N;
18.    cin >> N;
19.    string S;
20.    cin >> S;
21. 
22.    fenwick_tree<int> fw(2 * N + 1);
23.    fw.add(0 + N, 1);
24. 
25.    ll ps = 0, ans = 0;
26.    rep(i, 0, N)
27.    {
28.        if (S[i] == 'A')
29.            ps++;
30.        else if (S[i] == 'B')
31.            ps--;
32. 
33.        fw.add(ps + N, 1);
34.        ans += fw.sum(0, ps + N);
35.    }
36. 
37.    cout << ans << endl;
38. 
39.    return 0;
40.}