概要

高橋君と異なるランクのメンバーとペアになれる確率を、既約分数の形で求める問題です。

考察

高橋君（メンバー \(1\)）のランクを \(S_1\) とします。ペアが成立するのは、高橋君とは異なるランクを持つメンバーが選ばれたときだけです。

つまり、メンバー \(2\) から \(N\) の中で、\(S_1\) と異なるランクを持つ人数を数え、それを全体の候補者数 \(N - 1\) で割ったものが求める確率になります。

例えば、メンバー数 \(N = 5\) で、ランクが A B A B A の場合を考えます。高橋君（メンバー1）のランクは A です。メンバー2から5のランクは B, A, B, A で、このうち B が2人います。したがって、ペアが成立する確率は \(\frac{2}{4} = \frac{1}{2}\) です。

このように、単純に「異なるランクの人数」を数えるだけで確率の分子が求められます。分母は常に \(N - 1\) です。

最後に、この分数を既約分数にする必要があります。これは、分子と分母の最大公約数（GCD）で割ることで実現できます。

なお、この問題では \(N\) が最大で \(10^6\) あるため、愚直にシミュレーションしても間に合いますが、計算量的にも十分高速です。

アルゴリズム

1. 入力から \(N\) と各メンバーのランク列 \(S\) を受け取る。
2. 高橋君のランク \(S_1\) を取得する。
3. メンバー \(2\) 〜 \(N\) の中で、\(S_1\) と異なるランクの人数をカウントする。
4. このカウントが確率の分子、\(N - 1\) が分母となる。
5. 分子と分母の最大公約数を求め、それで割って既約分数にする。
6. 結果を P/Q の形式で出力する。

計算量

• 時間計算量: \(O(N + \log N)\)（GCDの計算に \(\log\) がかかる）
• 空間計算量: \(O(1)\)（入力を除けば定数メモリ）

実装のポイント

• 入力はスペース区切りの文字列なので、input().split() で簡単にリストにできる。

• 最大公約数を求めるには math.gcd() を使うと簡単。

• 分数が 0 または 1 になる場合も、問題文の指示通り 0/1 や 1/1 と出力されるので特に対応不要。

  ソースコード

import math

def main():
    N = int(input())
    S = input().split()
    
    s1 = S[0]
    others = S[1:]
    
    count_diff = 0
    for s in others:
        if s != s1:
            count_diff += 1
    
    total = N - 1
    gcd = math.gcd(count_diff, total)
    p = count_diff // gcd
    q = total // gcd
    print(f"{p}/{q}")

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。