概要

高橋君以外の \(N-1\) 人のメンバーの中から、高橋君と異なるランクを持つメンバーが選ばれる確率を求め、既約分数で出力する問題です。

考察

ペアが成立する条件は、「選ばれた相手が高橋君と異なるランクであること」です。 高橋君のランクは \(S_1\) なので、相手のランクが \(S_1\) が A であれば B、\(S_1\) が B であれば A のときにペアが成立します。

くじ引きの対象となるのは高橋君を除いた \(N-1\) 人です。この中からランダムに \(1\) 人が選ばれるため、すべての人が選ばれる確率は等しく \(\frac{1}{N-1}\) です。 したがって、ペアが成立する確率は以下の式で表せます。

\[ \frac{\text{高橋君と異なるランクの人の数（高橋君を除く）}}{N - 1} \]

条件を満たす人の数を \(C\) とすると、求める確率は \(\frac{C}{N-1}\) となります。 最後に、この分数を既約分数（これ以上約分できない分数）にする必要があります。これは、分子 \(C\) と分母 \(N-1\) の 最大公約数 (GCD) を求め、両方をその最大公約数で割ることで実現できます。

例えば、\(N=5\) で、高橋君を除く4人の中に条件を満たす人が2人いた場合、確率は \(\frac{2}{4}\) です。2と4の最大公約数は2なので、分子と分母をそれぞれ2で割って \(\frac{1}{2}\) となります。

アルゴリズム

1. 入力から \(N\) と各メンバーのランク \(S_1, S_2, \ldots, S_N\) を受け取ります。
2. 高橋君のランク \(S_1\) を確認し、探すべきランク（target）を決定します。
   • \(S_1\) が A なら target は B
   • \(S_1\) が B なら target は A
3. メンバー \(2\) から \(N\) の中で、ランクが target と一致する人の数 \(C\) を数えます。
4. 分母となる値を \(den = N - 1\) とします。
5. 分子 \(C\) と分母 \(den\) の最大公約数 \(g\) を計算します。
6. 分子と分母をそれぞれ \(g\) で割り、分子/分母 の形式で出力します。

計算量

• 時間計算量: \(O(N)\)
  • 入力の読み込みと、条件を満たすメンバーのカウントに \(O(N)\) の時間がかかります。
  • 最大公約数の計算は \(O(\log N)\) で非常に高速です。
  • 全体として \(O(N)\) となり、制約の \(N \le 10^6\) に対して十分高速に動作します。
• 空間計算量: \(O(N)\)
  • 入力された \(N\) 個のランクのデータを配列（リスト）として保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• 最大公約数の計算: Pythonでは標準ライブラリの math.gcd(a, b) を使うことで、簡単に最大公約数を求めることができます。

• 確率が0や1のケース: 確率が \(0\)（分子が \(0\)）の場合、最大公約数は分母と同じ値になるため、約分すると自動的に 0/1 になります。同様に確率が \(1\) の場合も 1/1 となるため、特別な条件分岐（if 文）を書く必要はありません。

• 高速な入出力: \(N\) が最大 \(10^6\) と大きいため、Pythonでは sys.stdin.read().split() を用いて入力を一括で読み込むと、実行時間を短縮でき Time Limit Exceeded (TLE) を防ぐことができます。

  ソースコード

import sys
import math

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    S1 = input_data[1]
    
    target = 'B' if S1 == 'A' else 'A'
    C = input_data[2:].count(target)
    
    den = N - 1
    g = math.gcd(C, den)
    
    print(f"{C // g}/{den // g}")

if __name__ == '__main__':
    main()

---

この解説は gemini-3.1-pro-thinking によって生成されました。