Tóm tắt đề bài

Cho một chuỗi độ dài \(n\) chỉ gồm ba ký tự C, A, và R. Hãy đếm số lượng dãy con CAR xuất hiện trong chuỗi đó. Một dãy con được tạo thành bằng cách chọn 3 vị trí \(i, j, k\) sao cho \(1 \le i < j < k \le n\) và các ký tự tại đó lần lượt là \(s_i = \text{'C'}\), \(s_j = \text{'A'}\), \(s_k = \text{'R'}\).

Phân tích

• Điều kiện: \(n \le 10^5\).
• Nhận xét:
  • Kết quả có thể rất lớn (vượt quá phạm vi của kiểu số nguyên 32-bit), do đó cần sử dụng kiểu dữ liệu số nguyên 64-bit (long long trong C++ hoặc mặc định trong Python).
  • Với mỗi ký tự A, số lượng bộ CAR mà nó đóng vai trò là chữ A ở giữa chính bằng: (số lượng chữ C đứng trước nó) \(\times\) (số lượng chữ R đứng sau nó).

Cách làm đơn giản (Brute Force)

Ý tưởng

Duyệt qua tất cả các bộ ba chỉ số \((i, j, k)\) thỏa mãn \(1 \le i < j < k \le n\). Nếu \(s_i = \text{'C'}\), \(s_j = \text{'A'}\) và \(s_k = \text{'R'}\) thì tăng biến đếm lên 1.

Độ phức tạp

• Thời gian: \(O(n^3)\)
• Đánh giá: Chỉ phù hợp với \(n \le 100\) (Subtask 1).

Code Brute Force

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    long long count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                if (s[i] == 'C' && s[j] == 'A' && s[k] == 'R') {
                    count++;
                }
            }
        }
    }
    cout << count << endl;
    return 0;
}

n = int(input())
s = input()
count = 0
for i in range(n):
    for j in range(i + 1, n):
        for k in range(j + 1, n):
            if s[i] == 'C' and s[j] == 'A' and s[k] == 'R':
                count += 1
print(count)

Hướng giải quyết (Tối ưu)

Nhận xét

Để tối ưu, thay vì duyệt 3 vòng lặp, ta có thể sử dụng kỹ thuật đếm hoặc quy hoạch động đơn giản:

1. Gọi countC là số lượng ký tự C đã gặp khi duyệt từ trái sang phải.
2. Gọi countCA là số lượng cặp CA đã hình thành được. Mỗi khi gặp một ký tự A, số lượng cặp CA mới được tạo thêm chính bằng số lượng ký tự C đang có trước đó.
3. Gọi countCAR là số lượng bộ CAR đã hình thành. Mỗi khi gặp một ký tự R, số lượng bộ CAR mới được tạo thêm chính bằng số lượng cặp CA đã có trước đó.

Thuật toán

1. Khởi tạo countC = 0, countCA = 0, countCAR = 0.
2. Duyệt qua từng ký tự \(s_i\) của chuỗi:
   • Nếu \(s_i = \text{'C'}\): countC++.
   • Nếu \(s_i = \text{'A'}\): countCA += countC.
   • Nếu \(s_i = \text{'R'}\): countCAR += countCA.
3. Kết quả cuối cùng là countCAR.

Độ phức tạp

• Thời gian: \(O(n)\) vì chỉ cần duyệt qua chuỗi một lần.
• Bộ nhớ: \(O(n)\) để lưu chuỗi (có thể tối ưu xuống \(O(1)\) nếu đọc từng ký tự).

Code tham khảo

#include <bits/stdc++.h>
using namespace std;

int main() {
    // Tối ưu tốc độ nhập xuất
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    string s;
    cin >> s;

    long long countC = 0;   // Đếm số chữ C
    long long countCA = 0;  // Đếm số cặp CA
    long long countCAR = 0; // Đếm số bộ CAR

    for (int i = 0; i < n; i++) {
        if (s[i] == 'C') {
            countC++;
        } else if (s[i] == 'A') {
            countCA += countC;
        } else if (s[i] == 'R') {
            countCAR += countCA;
        }
    }

    cout << countCAR << endl;

    return 0;
}

import sys

def solve():
    # Đọc n nhưng không nhất thiết phải dùng trong Python
    line1 = sys.stdin.readline()
    if not line1:
        return
    n = int(line1.strip())
    s = sys.stdin.readline().strip()

    count_c = 0   # Đếm số chữ C
    count_ca = 0  # Đếm số cặp CA
    count_car = 0 # Đếm số bộ CAR

    for char in s:
        if char == 'C':
            count_c += 1
        elif char == 'A':
            count_ca += count_c
        elif char == 'R':
            count_car += count_ca

    print(count_car)

if __name__ == "__main__":
    solve()