【AtCoder】ABC 447 D - Take ABC 2

2026-03-01

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 430 / NoviSteps: 2Q / 配点: 400 点

問題概要

A, B, Cの $3$ 種類の文字のみからなる文字列 $S$ が与えられる。文字列 $S$ に対して、以下で定義される操作を最大で何回操作を行うことができるかを求めよ。

$1 \le i \lt j \lt k \lt |S|$ かつ $S_i =$ A, $S_j =$ B, $S_k =$ Cを満たす $(i, j, k)$ の組を選び、 $S$ の $i, j, k$ 文字目を取り除く。残った文字を元の順序を保ったまま左に詰める。

制約

$1 \le |S| \le 10 ^{6}$

考察

前から順に文字を見ていき、採用できるA, B, Cが現れたらそれを採用していく貪欲法が成立する。サンプルケース1, 3を見ると分かりやすいかもしれない。

具体的には、以下のようなアルゴリズムとなる。

以下の3つのカウンターを用意しておく。
- cnt_A: これまでに見た文字のうち、Aの個数
- cnt_AB: これまでに見た文字のうち、Aの後にBが出現するパターンの個数
- cnt_ABC: これまでに見た文字のうち、Aの後にBが出現し、さらにその後ろにCが出現するパターンの個数
$S$ $S$ の先頭から順に文字を見ていき、以下の処理を行う。
- 文字がAのとき、cnt_Aを $1$ 増やす。
- 文字がBのとき、cnt_Aが $1$ 以上であれば、cnt_Aを $1$ 減らし、cnt_ABを $1$ 増やす。
- 文字がCのとき、cnt_ABが $1$ 以上であれば、cnt_ABを $1$ 減らし、cnt_ABCを $1$ 増やす。
最終的に、cnt_ABCが求めるべき答えとなる。

実装例

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.// ======================================== //
5. 
6.int main()
7.{
8.    string S;
9.    cin >> S;
10. 
11.    int cnt_a = 0, cnt_ab = 0;
12.    int ans = 0;
13.    for (auto &&c : S)
14.    {
15.        if (c == 'A')
16.        {
17.            cnt_a++;
18.        }
19.        else if (c == 'B')
20.        {
21.            if (cnt_a > 0)
22.            {
23.                cnt_a--;
24.                cnt_ab++;
25.            }
26.        }
27.        else if (c == 'C')
28.        {
29.            if (cnt_ab > 0)
30.            {
31.                cnt_ab--;
32.                ans++;
33.            }
34.        }
35.    }
36. 
37.    cout << ans << endl;
38. 
39.    return 0;
40.}