概要

\(N\) 個の文字列が与えられ、それぞれの文字列の中に含まれる感嘆符 ! の個数を数えます。その個数が \(K\) 個以上である文字列（元気な応援メッセージ）がいくつあるかを求める問題です。

考察

この問題を解くためには、各メッセージ \(S_i\) に対して「! が何個含まれているか」を正確に判定する必要があります。

1. 文字列の走査: 1つのメッセージの長さは最大で \(10^3\) です。文字列を先頭から 1 文字ずつ確認して ! をカウントしても十分間に合います。
2. 制約の確認: メッセージの総数は \(N \le 10^4\)、各メッセージの長さは \(|S_i| \le 10^3\) です。最悪の場合、全体で \(10^4 \times 10^3 = 10^7\) 文字を処理することになります。Python で処理する場合、標準的な input() を繰り返すよりも、一括で読み込むなどの工夫をするとより安全です。
3. 特殊なケース: メッセージの最大長が \(1000\) であるため、もし \(K > 1000\) であれば、どのメッセージも条件を満たすことはありません。この場合、即座に 0 と出力しても正解となります。

アルゴリズム

以下の手順で解を求めます。

1. 入力の取得: \(N, K\) と \(N\) 個の文字列 \(S_1, S_2, \dots, S_N\) を読み込みます。
2. カウント処理: 各 \(S_i\) について、以下のいずれかの方法で ! の個数を調べます。
   • 文字列の count('!') メソッドを使う。
   • 文字列を ! で分割（split）し、分割されたリストの要素数から計算する。
     • s.split('!') で得られるリストの長さが \(m\) のとき、含まれる ! の個数は \(m - 1\) 個です。
     • したがって、m - 1 >= k すなわち m > k であれば「元気な応援メッセージ」です。
3. 集計: 条件を満たすメッセージが見つかるたびに、答えとなる変数 energetic_count を \(1\) ずつ増やします。
4. 出力: 最終的な energetic_count を出力します。

計算量

• 時間計算量: \(O(\sum |S_i|)\)
  • 全てのメッセージの全文字を一度ずつ走査するため、文字数の総和に比例した時間がかかります。最大で \(10^7\) 文字程度であり、実行時間制限内に十分収まります。
• 空間計算量: \(O(\sum |S_i|)\)
  • 入力された全ての文字列をメモリ上に保持する場合の計算量です。

実装のポイント

• 効率的な入力: sys.stdin.read().split() を使うことで、空白や改行で区切られた入力を一括でリストとして取得できます。これにより、大量の入力データに対しても高速に処理を開始できます。

• 文字数カウントの工夫: Python の split('!') メソッドは内部が C 言語で実装されているため非常に高速です。リストの長さを比較するだけで条件判定ができるため、シンプルかつ効率的な実装になります。

  ソースコード

import sys

def main():
    # Read all input from standard input and split into tokens by whitespace.
    # This approach is efficient in Python and handles N, K, and all messages S_i.
    # Since S_i only contains letters, digits, and '!', it does not contain whitespace.
    data = sys.stdin.read().split()
    
    if not data:
        return

    # N: number of messages, K: minimum number of exclamation marks required.
    n = int(data[0])
    k = int(data[1])

    # The problem constraints state that each message S_i has a maximum length of 1000.
    # If the threshold K is greater than 1000, no message can possibly be "energetic".
    if k > 1000:
        print(0)
        return

    # We count "energetic" messages using a different approach from .count().
    # By splitting the string s by the exclamation mark '!', the resulting list 
    # of segments will have a length equal to (number of '!' characters) + 1.
    # Therefore, s.count('!') >= k is equivalent to len(s.split('!')) > k.
    
    energetic_count = 0
    # Messages are stored in the data list starting from index 2 up to index 2+n.
    for i in range(2, 2 + n):
        if i < len(data):
            # Applying the split-based counting logic
            if len(data[i].split('!')) > k:
                energetic_count += 1
    
    # Print the final count of energetic messages.
    print(energetic_count)

if __name__ == '__main__':
    main()

この解説は gemini-3-flash-preview によって生成されました。