概要

隣り合う参加者どうし（\(i\) と \(i+1\)）が握手するときに触れる手袋の色が同じになる回数、つまり \(R_i = L_{i+1}\) となるペアの数を数える問題です。

考察

握手が起こるのは「隣り合う2人」の間だけなので、判定すべき箇所は \(N-1\) 箇所しかありません。
各 \(i=1,2,\ldots,N-1\) について

• 左側の人 \(i\) の右手：\(R_i\)
• 右側の人 \(i+1\) の左手：\(L_{i+1}\)

が一致するかどうかを調べ、一致すれば「気まずい」なのでカウントします。

例えば \(N=4\) のとき、調べるのは次の3箇所です。

• \((1,2)\)：\(R_1\) と \(L_2\)
• \((2,3)\)：\(R_2\) と \(L_3\)
• \((3,4)\)：\(R_3\) と \(L_4\)

これをすべて確認すれば答えが出ます。

素朴に「全ペア（\(N(N-1)/2\)）を調べる」などをすると、隣り合い以外のペアまで見てしまい無駄が多く、\(N \le 2\times 10^5\) では \(O(N^2)\) となって間に合いません。
本問は隣接のみなので、1回ずつ見る \(O(N)\) で十分です。

アルゴリズム

1. \(N\) と各参加者の \((L_i, R_i)\) を入力で受け取る。
2. \(i=1\) から \(N-1\) まで順に、\(R_i\) と \(L_{i+1}\) を比較する。
3. 一致していればカウンタを \(+1\) する。
4. カウンタを出力する。

計算量

• 時間計算量: \(O(N)\)（隣接 \(N-1\) 箇所を1回ずつ比較）
• 空間計算量: \(O(N)\)（\(L, R\) を配列に保持するため）

実装のポイント

• 入力が最大 \(2\times 10^5\) 行なので、Python では sys.stdin.buffer.read() を使った高速入力にすると安全です。

• 判定は if R[i] == L[i+1]: の1行で済み、ミスが起きにくいです。

• この問題は配列を保持せず「前の \(R_i\) を覚えておき、次の \(L_{i+1}\) と比べる」形でも解けます（空間 \(O(1)\)）。ただし提示コードは分かりやすさ重視で配列に格納しています。

  ソースコード

import sys

def main():
    it = iter(sys.stdin.buffer.read().split())
    n = int(next(it))
    L = [None] * n
    R = [None] * n
    for i in range(n):
        L[i] = next(it).decode()
        R[i] = next(it).decode()

    ans = 0
    for i in range(n - 1):
        if R[i] == L[i + 1]:
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

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