概要

文字列 \(S\) の隣り合う文字を調べ、前が子供 C、後ろが大人 A になっている箇所を数えます。つまり、連続する文字列 CA の出現回数を求める問題です。

考察

重要なのは、子供と大人が隣り合っていることと、その順番が C → A であることです。

例えば、\(S=\) CCAAC の場合、前から \(2\) 番目の C と \(3\) 番目の A だけが条件を満たすため、答えは \(1\) です。\(1\) 番目の子供と \(3\) 番目の大人は隣り合っていないので、数えません。

この問題は、隣り合うすべての組を順番に調べる素朴な方法で十分高速に解けます。離れた子供と大人まで数えたり、逆順の AC を数えたりすると誤答になる点に注意しましょう。

提示されたコードでは、大人の位置に注目し、「その人が大人で、すぐ前の人が子供か」を確認しています。これは、問題文の条件を後ろ側の人から見たものです。

アルゴリズム

文字列の添字は \(0\) から始まるものとします。

1. 答えを保存する変数 cnt を \(0\) にします。
2. \(i=1,2,\ldots,N-1\) について、次の条件を確認します。
   • s[i] が A
   • s[i - 1] が C
3. 両方を満たしていれば、cnt を \(1\) 増やします。
4. 最後に cnt を出力します。

この走査では、隣り合うすべての組をちょうど一度ずつ調べます。そのうち CA になっている組だけを数えるので、求める個数が得られます。

計算量

• 時間計算量: \(O(N)\) — 隣り合う \(N-1\) 組を調べます。
• 空間計算量: \(O(N)\) — 入力文字列の保存に必要です。文字列を除く追加領域は \(O(1)\) です。

実装のポイント

• s[i - 1] を参照するため、ループは i = 1 から始めます。

• 文字列の最後の添字は \(N-1\) なので、ループ条件は i < n とします。

• \(N=1\) の場合は隣り合う組がありません。ループが一度も実行されず、そのまま正しい答えの \(0\) が出力されます。

  ソースコード

// 問題文から独立に実装: 各大人について、その直前が子供かを見る
#include <iostream>
#include <string>
int main() {
    int n; std::string s; std::cin >> n >> s;
    int cnt = 0;
    for (int i = 1; i < n; ++i) if (s[i] == 'A' && s[i - 1] == 'C') cnt++;
    std::cout << cnt << std::endl;
}

この解説は gpt-6-astra-medium によって生成されました。