概要

\(N\) 人の参加者が一列に並んでおり、隣り合うペアの「左側の人の右手」と「右側の人の左手」の色が同じ場合に「気まずい握手」となります。この気まずい握手が発生する箇所の総数を求める問題です。

考察

この問題を解くための重要なポイントは、「どの手とどの手が触れ合うのか」を正確に把握することです。

問題文によると、参加者 \(i\) と参加者 \(i+1\) が握手するとき、以下の 2 つの手が触れ合います。 - 参加者 \(i\) （左側）の右手： \(R_i\) - 参加者 \(i+1\) （右側）の左手： \(L_{i+1}\)

この \(R_i\) と \(L_{i+1}\) の色が一致しているかどうかを、すべての隣り合うペア（\(i = 1\) から \(N-1\) まで）について確認すればよいことになります。

例えば、3人の参加者の手袋が以下のような場合を考えます。 1. 参加者1: 左 \(L_1\)=N, 右 \(R_1\)=S 2. 参加者2: 左 \(L_2\)=S, 右 \(R_2\)=S 3. 参加者3: 左 \(L_3\)=N, 右 \(R_3\)=N

• 参加者1と2の握手： \(R_1\)(S) と \(L_2\)(S) を比較 \(\rightarrow\) 同じなので気まずい
• 参加者2と3の握手： \(R_2\)(S) と \(L_3\)(N) を比較 \(\rightarrow\) 異なるので良い握手

このように、隣り合う要素だけを順番に見ていけばよいため、1重のループで解くことができます。\(N\) は最大 \(2 \times 10^5\) ですが、この方法なら制限時間内に十分間に合います。

アルゴリズム

1. 参加者の人数 \(N\) と、各参加者の手袋の色 \(L_i, R_i\) を入力として受け取ります。
2. 気まずい握手の数を数える変数 awkward_count を 0 で初期化します。
3. \(i = 1\) から \(N-1\) まで、以下の処理を繰り返します。
   • 参加者 \(i\) の右手の色 \(R_i\) と、参加者 \(i+1\) の左手の色 \(L_{i+1}\) を比較する。
   • もし同じ色であれば、awkward_count を 1 加算する。
4. 最終的な awkward_count の値を出力します。

計算量

• 時間計算量: \(O(N)\)
  • \(N-1\) 個のペアを 1 回ずつ確認するため、参加者の数に比例した時間で計算が終わります。
• 空間計算量: \(O(N)\)
  • 全ての入力をリスト等に保持する場合、入力の大きさに比例したメモリを使用します。

実装のポイント

• 高速な入力: \(N\) が大きいため、Pythonでは sys.stdin.read().split() を使うことで、大量の入力を一括で取得し、高速に処理することができます。

• インデックスの管理: 入力データをフラットなリストとして取得する場合、参加者 \(i\) の右手 \(R_i\) と参加者 \(i+1\) の左手 \(L_{i+1}\) がリストのどの位置にあるかを正確に計算する必要があります。

  • 提示されたコードでは、tokens[2 * i] が \(R_i\)、tokens[2 * i + 1] が \(L_{i+1}\) に対応するようにループが組まれています。

    ソースコード

import sys

def solve():
    # 標準入力から全てのトークンを取得します。
    # sys.stdin.read().split() は大量の入力を高速に処理するのに適しています。
    tokens = sys.stdin.read().split()
    
    # 入力が空の場合の例外処理
    if not tokens:
        return
    
    # 参加者の人数 N
    n = int(tokens[0])
    
    # 気まずい握手の数をカウントする変数
    awkward_count = 0
    
    # 各参加者 i について、左手 L_i と右手 R_i の色は以下のように格納されています。
    # tokens[0] : N
    # tokens[1] : L_1, tokens[2] : R_1
    # tokens[3] : L_2, tokens[4] : R_2
    # ...
    # 一般に、参加者 i の右手 R_i は tokens[2 * i] に、
    # 参加者 i+1 の左手 L_{i+1} は tokens[2 * (i+1) - 1] = tokens[2 * i + 1] にあります。
    
    # i = 1 から N-1 までの隣り合うペアをチェックします。
    for i in range(1, n):
        # 参加者 i の右手 R_i
        r_i = tokens[2 * i]
        # 参加者 i+1 の左手 L_{i+1}
        l_next = tokens[2 * i + 1]
        
        # 手袋の色が同じであれば気まずい握手
        if r_i == l_next:
            awkward_count += 1
            
    # 結果を出力
    print(awkward_count)

if __name__ == "__main__":
    solve()

この解説は gemini-3-flash-preview によって生成されました。