概要

子供 C のすぐ後ろに大人 A がいる箇所、つまり文字列 \(S\) に部分文字列 "CA" が何回現れるかを求めます。

考察

条件を満たすのは、隣り合う \(2\) 文字がこの順に "CA" となる場所です。例えば、\(S =\) "CACAA" なら、先頭から \(1,2\) 文字目と \(3,4\) 文字目が "CA" なので、答えは \(2\) です。

隣り合う文字を先頭から順に調べる素朴な方法でも、時間計算量は \(O(N)\) であり、十分に間に合います。ただし、単に子供と大人の人数を数えたり、離れた位置にいる子供と大人を組にしたりしても、「すぐ後ろ」という条件を判定できません。

今回のコードでは、Python の count メソッドで "CA" の出現回数を直接数えます。

count は重ならない出現を数える点に注意が必要ですが、"CA" 同士が重なることはありません。重なるためには、ある文字が一方の末尾の A と、もう一方の先頭の C を同時に満たす必要があり、不可能だからです。したがって、s.count("CA") で条件を満たすすべての箇所を正しく数えられます。

アルゴリズム

1. 人数 \(N\) と文字列 \(S\) を読み込みます。
2. s.count("CA") で、部分文字列 "CA" の出現回数を求めます。
3. 求めた回数を出力します。

条件を満たす隣り合う \(2\) 人は必ず "CA" に対応し、逆に "CA" が現れる箇所は必ず条件を満たすため、この方法で正しい答えが得られます。

計算量

• 時間計算量: \(O(N)\)。長さ \(N\) の文字列から、長さ \(2\) の "CA" を探します。
• 空間計算量: \(O(N)\)。入力文字列の保存に必要です。入力文字列を除く追加領域は \(O(1)\) です。

実装のポイント

• 数えるのは "AC" ではなく "CA" です。文字列は列の前から後ろの順に並んでいます。

• \(N = 1\) の場合、隣り合う \(2\) 人は存在しません。count は自動的に \(0\) を返すため、特別な処理は不要です。

• \(N\) は入力として読み込みますが、count が文字列全体を調べるため、その後の計算では使用しません。

  ソースコード

# 問題文から独立に実装: 部分文字列 "CA" の出現回数（重ならないので count で十分）
n = int(input())
s = input().strip()
print(s.count("CA"))

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