概要

\(N\) 人が一列に並んでいるとき、隣り合う2人の握手で「気まずい握手」（手袋の色が同じ）になるペアの数を数える問題です。

考察

問題の整理

まず、問題文を整理しましょう。

• 参加者 \(i\) と参加者 \(i+1\) が握手するとき、参加者 \(i\) の右手と参加者 \(i+1\) の左手が触れ合います
• 触れ合う手袋の色が同じなら「気まずい握手」
• \(i = 1, 2, \ldots, N-1\) の全てのペアについて、気まずい握手の数を数えます

具体例で考える

例えば、3人の参加者がいて以下のような手袋をしているとします：

• 参加者1と参加者2の握手：参加者1の右手(S) vs 参加者2の左手(S) → 同じ色 → 気まずい握手
• 参加者2と参加者3の握手：参加者2の右手(N) vs 参加者3の左手(N) → 同じ色 → 気まずい握手

答えは \(2\) です。

素朴なアプローチで十分

この問題では、\(N-1\) 組の隣り合うペアそれぞれについて、手袋の色を1回比較するだけで済みます。特別な工夫は不要で、単純なループで \(O(N)\) で解けます。

アルゴリズム

1. \(N\) 人分の手袋の情報（左手 \(L_i\)、右手 \(R_i\)）を読み込んで配列に格納する
2. カウンタ count を \(0\) で初期化する
3. \(i = 0, 1, \ldots, N-2\) について（0-indexed）：
   • 参加者 \(i\) の右手の色 gloves[i][1] と参加者 \(i+1\) の左手の色 gloves[i+1][0] を比較
   • 同じ色なら count を \(1\) 増やす
4. count を出力する

計算量

• 時間計算量: \(O(N)\)
  • 入力の読み込みに \(O(N)\)
  • ペアの比較に \(O(N-1) = O(N)\)
• 空間計算量: \(O(N)\)
  • 全参加者の手袋情報を配列に格納するため

実装のポイント

• Pythonでは input().split() で左手と右手の色を一度に読み込めます

• 配列のインデックスに注意：コード中では0-indexedなので、参加者 \(i\)（1-indexed）はインデックス \(i-1\) に対応します

• 比較は単純な文字列比較 == で行えます（'N' == 'N' は True、'N' == 'S' は False）

  ソースコード

n = int(input())
gloves = []
for _ in range(n):
    l, r = input().split()
    gloves.append((l, r))

count = 0
for i in range(n - 1):
    # 参加者iの右手と参加者i+1の左手を比較
    if gloves[i][1] == gloves[i + 1][0]:
        count += 1

print(count)

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