概要

高橋君（メンバー1）とランクが異なる相手がくじで選ばれる確率を、既約分数で求める問題です。

考察

くじで選ばれるのはメンバー \(2 \sim N\) のうちの1人で、全員が同確率 \(\frac{1}{N-1}\) で選ばれます。
したがって「ペアが成立する（＝ランクが異なる）」確率は、

• 分子：\(2 \sim N\) の中で 高橋君とランクが異なる人数
• 分母：候補人数である \(N-1\)

の比になります。

つまり答えは [ \frac{#{i \in [2,N] : S_i \neq S_1}}{N-1} ] です。

素朴に S = input().split() のようにして全員分の文字列をリストにすると、\(N \le 10^6\) で入力が大きく、Pythonではメモリ使用量が増えたり速度が落ちたりしがちです（TLE/メモリ面のリスク）。
そこで、入力をバイト列として読み取り、A/B だけを数えることで、余計な文字列生成を避けて高速・省メモリに処理します。

また、出力は既約分数なので \(\gcd\) で約分が必要です。
確率が \(0\) や \(1\) のときは 0/1, 1/1 と指定されているので、そこも分岐します。

アルゴリズム

1. \(N\) を読む。
2. 残りの入力をバイト列として読み、A または B の文字だけを順に拾う。
   • 1つ目に現れたランクを \(S_1\)（高橋君のランク）として記録。
   • 2つ目以降（メンバー2以降）で \(S_1\) と同じランクの人数 same を数える。
3. 異なるランクの人数は diff = (N-1) - same。
4. 確率は \(\frac{\text{diff}}{N-1}\)。
   
   • diff == 0 なら 0/1
   • diff == N-1 なら 1/1
   • それ以外は \(g=\gcd(\text{diff}, N-1)\) で約分して diff/g と (N-1)/g を出力。

例：\(N=5\), ランクが A B A B B のとき
高橋君は A、メンバー2〜5は B A B B。
異なる（B）が3人なので確率は \(\frac{3}{4}\) です。

計算量

• 時間計算量: \(O(N)\)（A/B を \(N\) 個数えるだけ）
• 空間計算量: \(O(1)\)（人数カウントなど定数個の変数のみ）

実装のポイント

• 入力サイズが大きいので、split() で巨大なリストを作らず、sys.stdin.buffer.read() でまとめて読み、バイト列から A/B のみを数えると高速です。

• 既約分数にするために math.gcd で約分します。

• diff=0（必ず不成立）や diff=N-1（必ず成立）のケースは、指定通り 0/1, 1/1 を出力します。

  ソースコード

import sys
import math

def main():
    buf = sys.stdin.buffer
    N_line = buf.readline()
    while N_line.strip() == b"":
        N_line = buf.readline()
    N = int(N_line)

    rest = buf.read()
    s1 = None
    same = 0
    cnt = 0  # number of ranks read

    for b in rest:
        if b == 65 or b == 66:  # 'A' or 'B'
            cnt += 1
            if cnt == 1:
                s1 = b
            else:
                if b == s1:
                    same += 1
            if cnt == N:
                break

    diff = (N - 1) - same
    if diff == 0:
        print("0/1")
        return
    if diff == N - 1:
        print("1/1")
        return

    g = math.gcd(diff, N - 1)
    print(f"{diff // g}/{(N - 1) // g}")

if __name__ == "__main__":
    main()

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