概要

\(N\) 人のお客さんについて、実際の注文 \(T_i\) とキッチンへの伝達 \(S_i\) を比較し、異なっているものの個数を数える問題です。

考察

この問題は非常にシンプルで、各お客さんについて2つの文字列が一致するかどうかを判定するだけです。

• 重要な気づき: 各お客さんは独立しており、\(T_i\) と \(S_i\) の組をそれぞれ比較すればよいです。他のお客さんの注文との関係を考える必要はありません。
• 素朴なアプローチで十分か？: \(N\) 人それぞれについて文字列比較を1回行うだけなので、\(N \leq 10^5\) かつ文字列の長さが最大 \(20\) であれば、素朴に1つずつ比較するだけで十分高速です。特別なアルゴリズムは不要です。

具体例

例えば \(N = 3\) で以下の入力があったとします：

不一致は \(i = 2\) の1人だけなので、答えは 1 です。

アルゴリズム

1. \(N\) を読み込む。
2. カウンタ count を \(0\) で初期化する。
3. \(N\) 回ループし、各行で \(T_i\) と \(S_i\) を読み込む。
4. \(T_i \neq S_i\) ならば count を \(1\) 増やす。
5. 最後に count を出力する。

計算量

• 時間計算量: \(O(N \times L)\)（\(L\) は文字列の最大長で、本問では \(L \leq 20\)）
  • 各お客さんについて文字列比較に \(O(L)\) かかり、それを \(N\) 回繰り返します。\(L\) が定数とみなせるので、実質 \(O(N)\) です。
• 空間計算量: \(O(L)\)
  • 各行の \(T_i\), \(S_i\) を保持するだけで、全データを保存する必要はありません。

実装のポイント

• Python では input().split() で1行をスペース区切りで分割し、2つの文字列を同時に受け取れます。

• 文字列の比較は != 演算子で簡単に行えます。Python の文字列比較は内容（中身の文字列）で判定されるため、安心してそのまま使えます。

  ソースコード

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

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