概要

参加者が一列に並んでおり、隣り合うペアのうち、右手と左手の手袋の色が一致している（気まずい握手）になるペアの数を数える問題。

考察

この問題では、各参加者 \(i\) に対して、右手の手袋の色 \(R_i\) と、次の参加者 \(i+1\) の左手の手袋の色 \(L_{i+1}\) を比較します。もし \(R_i = L_{i+1}\) であれば、そのペアは「気まずい握手」となります。

素朴なアプローチとして、すべての隣接ペアに対してこの比較を行う方法があります。制約が \(N \leq 2 \times 10^5\) なので、この比較をすべて行っても十分間に合います（後述の計算量参照）。

重要なのは、手袋の色が文字 N（紺色）または S（白色）のどちらかであること。これらを単純に文字列として比較すればよいので、特別な前処理や変換は必要ありません。

アルゴリズム

1. 各参加者の手袋の情報を読み込み、リストなどに保存する。
2. 隣接するペア \((i, i+1)\) について、参加者 \(i\) の右手の色 \(R_i\) と参加者 \(i+1\) の左手の色 \(L_{i+1}\) が等しいかどうかをチェックする。
3. 等しければカウントを増やす。
4. 最終的なカウントを出力する。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

時間計算量は、すべての隣接ペアを一度だけ調べるため、線形時間で処理できます。空間計算量は、全参加者の情報を保存するために \(N\) 個分のデータが必要です。

実装のポイント

• 手袋の色は文字列として扱うことができるので、そのまま比較すればOK。
• 入力は "N S" のような形式なので、split() を使って簡単に左右の色を取得できる。
• インデックスの範囲外アクセスに注意（最後の参加者からは次の人がいないので、ループは \(i = 0\) から \(N-2\) まで回す）。

ソースコード

N = int(input())
gloves = [input().split() for _ in range(N)]

count = 0
for i in range(N - 1):
    if gloves[i][1] == gloves[i + 1][0]:
        count += 1

print(count)

この解説は qwen3-coder-480b によって生成されました。