概要

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

考察

高橋君を除く \(N-1\) 人から \(1\) 人が等確率で選ばれます。ペアが成立するのは、選ばれた相手のランクが高橋君と異なる場合です。

例えば、\(N = 5\)、ランクが A A B B A の場合を考えます。

• 高橋君のランクは A
• メンバー \(2 \sim 5\) のランクは A B B A
• このうちランクが異なる（B である）メンバーは \(2\) 人

よって、ペアが成立する確率は \(\frac{2}{4} = \frac{1}{2}\) となります。

一般に、メンバー \(2, 3, \ldots, N\) の中で高橋君とランクが異なる人数を \(D\) とすれば、求める確率は：

\[\frac{D}{N-1}\]

これを既約分数にするために、分子と分母の最大公約数（\(\gcd\)）で割ればよいです。

この問題は素朴にメンバー全員を一度走査するだけで解けるため、特別な工夫は不要です。\(N\) が最大 \(10^6\) ですが、\(O(N)\) の走査で十分間に合います。

アルゴリズム

1. 高橋君のランク \(S_1\) を記録する。
2. メンバー \(2\) からメンバー \(N\) までを走査し、ランクが \(S_1\) と異なる人数 \(D\) を数える。
3. 分子 \(P = D\)、分母 \(Q = N - 1\) とする。
4. \(g = \gcd(P, Q)\) を求め、\(P\) と \(Q\) をそれぞれ \(g\) で割って既約分数にする。
5. P/Q の形式で出力する。

注意: \(D = 0\)（全員同じランク）の場合は \(\gcd(0, Q) = Q\) となるため、\(0 / Q = 0 / 1\) が正しく出力されます。同様に \(D = N-1\)（全員異なるランク）の場合は \(\frac{N-1}{N-1} = \frac{1}{1}\) となります。

計算量

• 時間計算量: \(O(N)\)（メンバー全員を一度走査するだけ）
• 空間計算量: \(O(N)\)（入力の格納に必要。ランクをカウントするだけなら \(O(1)\) でも可能）

実装のポイント

• math.gcd を使えば最大公約数を簡単に計算できます。Python の math.gcd は引数に \(0\) が含まれていても正しく動作します（\(\gcd(0, k) = k\)）。

• 既約分数の出力フォーマットが P/Q であることに注意してください。f-string を使うと f"{P}/{Q}" で簡潔に書けます。

• メンバーのインデックスは \(0\)-indexed で管理しているため、S[0] が高橋君のランク、S[1] 〜 S[N-1] がメンバー \(2\) 〜 \(N\) のランクに対応します。

  ソースコード

import math

N = int(input())
S = input().split()

takahashi_rank = S[0]

# Count members 2..N with different rank
different = sum(1 for i in range(1, N) if S[i] != takahashi_rank)

P = different
Q = N - 1

g = math.gcd(P, Q)
P //= g
Q //= g

print(f"{P}/{Q}")

---

この解説は claude4.6opus-thinking によって生成されました。