概要

高橋君と異なるランクのメンバーが選ばれたときにのみペアが成立する確率を、既約分数で求める問題です。

考察

高橋君（メンバー1）のランクを \(S_1\) とします。ペアが成立するためには、くじ引きで選ばれる相手が高橋君とは異なるランク（\(S_1\) が A なら B、B なら A）でなければなりません。

\(N-1\) 人の中からランダムに1人選ぶので、確率は「高橋君と異なるランクの人数」を「候補者の総数（\(N-1\)）」で割った値になります。

アルゴリズム

1. 高橋君のランク \(S_1\) を取得する
2. メンバー2からNまでの各メンバーについて、\(S_1\) と異なるランクの人数を数える
3. 確率 = (異なるランクの人数) / (\(N-1\))
4. この分数を約分して既約分数の形で出力する

計算量

• 時間計算量: \(O(N)\)
  • メンバーのランクを1回走査するため
• 空間計算量: \(O(N)\)
  • 入力のランク情報を保持するため

実装のポイント

• 高橋君自身（メンバー1）は候補から除外する必要があるため、インデックス1からループを開始する

• 分数の約分には math.gcd 関数を使用する

• 確率が0の場合は 0/1、1の場合は 1/1 と出力するが、アルゴリズム上自然に処理できる

  ソースコード

def main():
    import sys
    data = sys.stdin.read().splitlines()
    n = int(data[0].strip())
    S = data[1].split()
    
    high = S[0]
    count_other = 0
    total_other = n - 1
    
    for i in range(1, n):
        if S[i] != high:
            count_other += 1
            
    from math import gcd
    g = gcd(count_other, total_other)
    p = count_other // g
    q = total_other // g
    
    print(f"{p}/{q}")

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。