概要

\(N\) 個のメッセージの中から、感嘆符 ! が \(K\) 個以上含まれている「元気な応援メッセージ」の数を数える問題です。

考察

この問題で重要な気づきは以下の通りです：

1. 各メッセージは独立して判定できる: メッセージ同士の関係を考える必要はなく、1つずつ順番に調べればよいです。

2. 判定条件はシンプル: 各メッセージについて、! の出現回数を数えて \(K\) 以上かどうかを確認するだけです。

具体例で考える

例えば、\(N = 3\)、\(K = 2\) で以下のメッセージがあるとします： - Ganbare!! → ! が2個 → \(2 \geq 2\) なので「元気」✓ - Hello → ! が0個 → \(0 \geq 2\) ではないので「元気でない」✗ - Go!!!Go! → ! が4個 → \(4 \geq 2\) なので「元気」✓

この場合、答えは \(2\) となります。

素朴なアプローチで十分な理由

この問題では、各メッセージの長さが最大 \(10^3\)、メッセージ数が最大 \(10^4\) なので、全てのメッセージの全ての文字を調べても最大 \(10^3 \times 10^4 = 10^7\) 回の操作で済みます。これは十分高速に処理できる範囲です。

アルゴリズム

1. 「元気な応援メッセージ」の数を記録する変数 count を \(0\) で初期化する
2. \(N\) 個の各メッセージ \(S_i\) について以下を繰り返す：
   • 文字列 \(S_i\) 内の ! の個数を数える
   • ! の個数が \(K\) 以上であれば、count を \(1\) 増やす
3. 最終的な count の値を出力する

Pythonでは、文字列のメソッド S.count('!') を使うことで、文字列 \(S\) 内の ! の個数を簡単に数えることができます。

計算量

• 時間計算量: \(O(N \times L)\)
  • \(L\) は各メッセージの長さの最大値（最大 \(10^3\)）
  • 各メッセージに対して count() メソッドで全文字を走査するため
• 空間計算量: \(O(L)\)
  • 各メッセージを1つずつ読み込んで処理するため、1つのメッセージを格納する領域のみ必要

実装のポイント

• Pythonの count() メソッドを活用することで、特定の文字の出現回数を簡潔に取得できます

• メッセージを1つずつ読み込んで処理すれば、全メッセージを配列に保存する必要がなく、メモリ効率が良くなります

• 条件は「\(K\) 以上」なので、>= を使うことに注意しましょう（> ではありません）

  ソースコード

N, K = map(int, input().split())
count = 0
for _ in range(N):
    S = input()
    if S.count('!') >= K:
        count += 1
print(count)

この解説は claude4.5opus によって生成されました。