Pythonで競合のない最高スコアのチームを見つけるプログラム

バスケットボールの試合を想定し、2つのリスト「scores」と「ages」が与えられているとします。scores[i] と ages[i] は、それぞれ i 番目のプレイヤーのスコアと年齢を表します。目的は、合計スコアが最も高いチームを選出することです。チームのスコアは、所属する全プレイヤーのスコアの総和として定義されます。

ただし、試合では「競合」が許されません。競合とは、より若いプレイヤーが、より年上のプレイヤーよりも厳密に高いスコアを持っている状態を指します。

例えば、入力が scores = [5,7,9,14,19]、ages = [5,6,7,8,9] の場合、出力は 54 になります。このケースではすべてのプレイヤーを競合なく選択できるためです。

アルゴリズムの考え方

まず、(年齢, スコア) のペアを作成して年齢順にソートします。これにより、リストの後ろに位置するプレイヤーほど年長であることが保証されます。そのうえで動的計画法(DP)を適用します。dp[i] は「i 番目のプレイヤーを必ず選ぶ場合の、競合のない最大合計スコア」を表します。

各 i に対して、それ以前のプレイヤー j のうち scores[j] <= scores[i](年下または同年齢で、スコアが i 番目以下)を満たすものだけを先に選べるため、dp[j] + scores[i] との最大値を dp[i] に反映します。最終的な答えは dp 配列全体の最大値となり、計算量は O(n²) です。

解決手順

• ages と scores の対応する要素からペア (a, s) を作成し、リスト sa を構築する
• sa をソートする
• ソート後の sa からスコアのみを抽出したリストを作る
• maxScore := 0 で初期化する
• n := scores のサイズとする
• dp := 長さ n の配列を 0 で初期化する
• i を 0 から n-1 まで繰り返す
  • score := scores[i]
  • dp[i] := score
  • j を 0 から i-1 まで繰り返す
    • scores[j] <= score ならば、dp[i] := max(dp[i], dp[j] + score)
  • maxScore := max(maxScore, dp[i])
• maxScore を返す

実装例

以下の Python コードで実際の動作を確認できます。

def solve(scores, ages):
    sa = [[a,s] for a,s in zip(ages,scores)]

    sa.sort()
    scores = [s for a,s in sa]

    maxScore = 0
    n = len(scores)
    dp = [0] * n

    for i in range(n):
        score = scores[i]
        dp[i] = score

        for j in range(i):
            if scores[j] <= score:
                dp[i] = max(dp[i], dp[j] + score)
        maxScore = max(maxScore, dp[i])

    return maxScore

scores = [5,7,9,14,19]
ages = [5,6,7,8,9]
print(solve(scores, ages))

入力

[5,7,9,14,19], [5,6,7,8,9]

出力

54