概要

文字列 \(S\) の隣り合う \(2\) 文字を調べ、CA になっている箇所の個数を数えます。

考察

子供は C、大人は A で表されます。したがって、「子供のすぐ後ろに大人がいる」という条件は、文字列中で C の直後に A があることと同じです。

例えば、\(S =\) CCAAC の場合、隣り合う \(2\) 文字は前から順に次のようになります。

• CC：条件を満たさない
• CA：条件を満たす
• AA：条件を満たさない
• AC：条件を満たさない

よって、答えは \(1\) です。

この問題では、隣り合う文字をすべて確認する素朴な方法で十分高速に解けます。大人と子供のすべての組み合わせを調べる必要はありません。

また、子供より後ろにいる大人をすべて数えると、「すぐ後ろ」という条件を満たさない人まで数えてしまいます。必ず隣り合う位置だけを調べましょう。

アルゴリズム

1. 答えを表す変数 ans を \(0\) にします。
2. \(0\) 始まりの添字で、\(i = 0, 1, \ldots, N-2\) を順に調べます。
3. s[i] が C、かつ s[i + 1] が A なら、ans に \(1\) を加えます。
4. ans を出力します。

条件を満たす箇所は必ず隣り合う \(2\) 文字に対応します。この方法では、そのすべてをちょうど一度ずつ調べるため、正しい個数が得られます。

計算量

• 時間計算量: \(O(N)\)
  隣り合う \(N-1\) 組をそれぞれ一度ずつ確認します。
• 空間計算量: \(O(N)\)
  入力文字列の保持に必要です。入力を除く追加の作業領域は \(O(1)\) です。

実装のポイント

• Python の文字列の添字は \(0\) から始まります。s[i + 1] が範囲外にならないように、ループには range(n - 1) を使います。

• CA と AC は異なります。子供が前、大人が後ろなので、条件は s[i] == 'C' and s[i + 1] == 'A' です。

• 正解コードでは、条件を満たすたびに \(1\) を生成し、sum で合計しています。ジェネレータ式なので、集計用のリストは作りません。

• \(N=1\) の場合、隣り合う人はいません。range(n - 1) は空になり、sum は \(0\) を返すため、特別な処理は不要です。

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    s = data[1]
    ans = sum(1 for i in range(n - 1) if s[i] == 'C' and s[i + 1] == 'A')
    print(ans)

main()

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