Pythonで最終戦後に優勝できるスイマーの人数を求めるプログラム

問題の概要

長さ n の数値リスト nums が与えられます。各要素は、水泳競技会に参加しているスイマーの現在の得点を表しています。最終戦では、このラウンドの1位の選手に n 点、2位の選手に n-1 点というように、順位に応じた得点が加算されます。ここで、現時点から見て、最終戦の結果次第でまだ優勝(1位タイを含む)の可能性を残しているスイマーが何人いるかを求めます。得点が並んで1位タイになった場合も優勝としてカウントします。

入力例とその解釈

たとえば入力が nums = [9, 6, 11, 12] の場合、出力は 3 になります。これは、現在 9 点・11 点・12 点のスイマーは、最終得点が [13, 9, 13, 13] となるような順位結果を実現できれば優勝できるためです。

具体的な順位の割り当ては次の通りです。

• 9 点のスイマーが1位 → 4 点加算で合計 13 点
• 6 点のスイマーが2位 → 3 点加算で合計 9 点
• 11 点のスイマーが3位 → 2 点加算で合計 13 点
• 12 点のスイマーが4位(最下位)→ 1 点加算で合計 13 点

一方、6 点のスイマーについて考えてみましょう。仮に1位になっても最終得点は 10 点(6 + 4)にとどまります。たとえ自分が1位で 9 点のスイマーが2位になって 12 点になったとしても、それ以上の得点を持つスイマーには追いつけず、どんな結果になっても優勝は不可能です。したがって、優勝の可能性があるのは 3 人ということになります。

解法のステップ

この問題は、次の手順で解くことができます。

• nums が空であれば 0 を返す
• n := nums のサイズ
• ans := 0(答えを格納する変数)
• nums を昇順にソートする
• a := 0
• i を n-1 から 0 まで 1 ずつ減らしながら繰り返す
  • cand := nums[i] + n - i
  • cand > a であれば a := cand
• nums の各要素 x について
  • x + n >= a であれば ans := ans + 1
• ans を返す

なぜこのアルゴリズムで正しく判定できるのか

鍵となる考え方は次の2点です。

• スイマーが到達できる最高得点: 最終戦で1位を取れば n 点が加算されるため、各スイマーの理論上の最大得点は「現在の得点 + n」です。
• 優勝ラインの最小値: 得点の低いスイマーほど高い配点(n 点、n-1 点…)を与えるように順位を割り当てると、トップの得点を最小化できます。昇順ソート後の i 番目(0始まり)のスイマーに n-i 点が与えられると考えると、そのときの得点は nums[i] + n - i となり、この最大値 a が「優勝に必要な得点の最低ライン」になります。

したがって、「現在の得点 + n」が a 以上のスイマーは、最適な順位結果のもとで少なくとも1位タイになれるため、優勝の可能性ありと判定できます。

Pythonでの実装例

理解を深めるために、以下の実装を見てみましょう。

def solve(nums):
    if not nums:
        return 0
    n = len(nums)
    ans = 0
    nums.sort()
    a = 0
    for i in range(n - 1, -1, -1):
        cand = nums[i] + n - i
        if cand > a:
            a = cand
    for x in nums:
        if x + n >= a:
            ans += 1
    return ans

nums = [9, 6, 11, 12]
print(solve(nums))

入力

[9, 6, 11, 12]

出力

3

計算量

ソートに O(n log n)、その後の2つの走査にそれぞれ O(n) かかるため、全体の時間計算量は O(n log n) です。ソートをリスト自体に対して行う場合、追加の空間計算量は O(1) で済みます。