概要

各お客さんについて、実際の注文 \(T_i\) と伝達した注文 \(S_i\) を1組ずつ比較し、異なっている組の数を数えるだけの問題です。
つまり「\(T_i \neq S_i\) となる \(i\) の個数」を求めればよいです。

考察

重要な観察はシンプルで、各お客さんの判定は他のお客さんと独立です。
したがって、全体を通して複雑なデータ構造や並べ替えは不要で、1行ずつ読んで比較してカウントすれば解けます。

例えば次のような入力を考えると：

• \((T_1, S_1) = (\text{ramen}, \text{ramen})\) → 一致（カウントしない）
• \((T_2, S_2) = (\text{sushi}, \text{susi})\) → 不一致（+1）
• \((T_3, S_3) = (\text{curry}, \text{curry})\) → 一致

答えは 1 です。

素朴なアプローチとして、全組を配列に保存して後で処理する方法もありますが、この問題ではその必要はありません。
入力を受け取るたびに比較すればよく、メモリも節約できます。
\(N \le 10^5\) なので、1回ずつ比較する \(O(N)\) 解法で十分高速です。

アルゴリズム

1. 整数 \(N\) を読む。
2. 変数 ans = 0 を用意する（間違い件数）。
3. \(N\) 回繰り返す：
   • 文字列 t, s を読む。
   • t != s なら ans += 1。
4. 最後に ans を出力する。

このまま実装したものが提示コードです。

計算量

• 時間計算量: \(O(N)\)
  （各行で文字列比較を1回ずつ行うため）
• 空間計算量: \(O(1)\)
  （入力を保持せず、その場で判定するため）

実装のポイント

• 入力件数が最大 \(10^5\) なので、Python では sys.stdin.readline を使うと安定して速いです。

• 各行は input().split() で t, s の2つに分解できます。

• 比較条件はそのまま if t != s: でOKです。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    n = int(input().strip())
    ans = 0
    for _ in range(n):
        t, s = input().split()
        if t != s:
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

この解説は gpt-5.3-codex によって生成されました。