概要

\(N\) 人の客が実際に注文した料理名 \(T_i\) と、店員がキッチンに伝えた料理名 \(S_i\) が与えられます。\(T_i\) と \(S_i\) が一致していない客が何人いるかを求める問題です。

考察

この問題で求められているのは、すべての客 \(i\) について「\(T_i\) と \(S_i\) が等しいか？」を確認し、等しくないものの個数をカウントすることです。

客の人数 \(N\) は最大で \(10^5\) であり、料理名の長さも最大 20 文字と短いため、各客の注文を一つずつ順番にチェックしていく素直な方法で十分に間に合います。

具体的には、以下の手順で進めます。 1. 間違えた人数を数える変数 count を 0 で初期化する。 2. 1番目から \(N\) 番目までの客について、以下の処理を繰り返す。 - もし \(T_i\) が \(S_i\) と異なる（\(T_i \neq S_i\)）ならば、count に 1 を加える。 3. 最終的な count の値を出力する。

アルゴリズム

1. 入力の受け取り: \(N\) および各ペア \((T_i, S_i)\) を取得します。
2. 反復処理: ループ（for文）を用いて、各客のデータを走査します。
3. 条件判定: 文字列の比較演算子（Pythonでは !=）を用いて、注文内容が一致するか判定します。
4. 集計: 条件を満たした回数を記録します。

計算量

• 時間計算量: \(O(N \times L)\)
  • \(N\) 人の客を一度ずつ確認するため \(O(N)\) です。各確認において文字列の比較に料理名の長さ \(L\)（最大20）に比例する時間がかかりますが、\(L\) は十分小さいため、全体として非常に高速に動作します。
• 空間計算量: \(O(N \times L)\)
  • 入力されたすべての文字列をメモリに保持する場合、この計算量となります。

実装のポイント

• 高速な入力: \(N\) が \(10^5\) と比較的大きいため、Pythonで input() を何度も呼び出すよりも、sys.stdin.read().split() を使って一括で入力を取得して処理する方が実行時間を短縮できます。

• 文字列の比較: Pythonでは t != s のように書くだけで、文字列の中身が異なっているかどうかを簡単に判定できます。

  ソースコード

import sys

def main():
    # 標準入力から全データを取得し、空白・改行で分割する
    data = sys.stdin.read().split()
    if not data:
        return
    
    # 1つ目の要素は人数 N
    n = int(data[0])
    
    count = 0
    # 2つ目以降の要素を T_i, S_i のペアとして処理する
    for i in range(n):
        t = data[2 * i + 1]
        s = data[2 * i + 2]
        # 実際の注文と伝達が異なればカウント
        if t != s:
            count += 1
            
    # 結果を出力
    print(count)

if __name__ == '__main__':
    main()

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