概要

曲をいくつ選ぶかと、各ジャンルから何曲選ぶかに注目します。
「偏りスコアを \(x\) 以下にできる条件」をジャンルごとの選択曲数の上限に言い換え、その上限のもとで選べる最大再生時間を DP で求めます。

考察

まず、ある曲集合を選んだ後、それを並べ替えて偏りスコアを \(x\) 以下にできる条件を考えます。

選んだ曲数を \(s\)、あるジャンルの曲数を \(c\) とします。
このジャンル以外の曲は \(s-c\) 曲あります。

この \(s-c\) 曲を並べると、その前後や間に、このジャンルの曲を入れられる「隙間」が \(s-c+1\) 個できます。

例えば、他ジャンルの曲が ○ だとすると、

_ ○ _ ○ _ ○ _

のように、隙間は \(4\) 個あります。

偏りスコアを \(x\) 以下にしたいなら、各隙間に同じジャンルの曲を高々 \(x\) 曲までしか置けません。
したがって必要な条件は

\[ c \leq x(s-c+1) \]

です。これを変形すると、

\[ (x+1)c \leq x(s+1) \]

なので、

\[ c \leq \left\lfloor \frac{x(s+1)}{x+1} \right\rfloor \]

となります。

実はこの条件は十分条件でもあります。
つまり、選んだ \(s\) 曲について、すべてのジャンルの選択数が

\[ \left\lfloor \frac{x(s+1)}{x+1} \right\rfloor \]

以下なら、偏りスコアを \(x\) 以下に並べることができます。

よって、偏りスコア \(x\) が可能かどうかは、

ある曲数 \(s\) について、各ジャンルから高々
\(L = \left\lfloor \frac{x(s+1)}{x+1} \right\rfloor\) 曲まで選ぶという制限のもとで、
合計再生時間を \(K\) 秒以上にできるか

を判定すればよいです。

---

次に、各ジャンルから何曲選ぶかを考えます。

あるジャンルから \(t\) 曲選ぶと決めたなら、再生時間の合計を最大にするには、そのジャンルの中で再生時間が長い順に \(t\) 曲選べばよいです。

そのため、ジャンルごとに曲の再生時間を降順ソートし、累積和を持っておきます。

例えば、あるジャンルの曲の再生時間が

\[ 10, 7, 4 \]

なら、累積和は

\[ 0, 10, 17, 21 \]

です。
このジャンルから \(2\) 曲選ぶときの最大再生時間は \(17\) 秒です。

---

素朴に曲集合を全探索すると \(2^{2N}\) 通りあり、最大で \(2^{300}\) 通りになるため不可能です。
また、\(K\) は最大 \(10^9\) なので、再生時間を DP の状態にすることもできません。

そこで、「選んだ曲数」を DP の状態にします。

アルゴリズム

曲数を \(M = 2N\) とします。

まず、次の DP を考えます。

\[ F[L][s] = \]

各ジャンルから高々 \(L\) 曲まで選べるとき、合計でちょうど \(s\) 曲選んだ場合の最大再生時間。

この \(F[L][s]\) を、すべての \(L\) について前計算します。

DP の作り方

ジャンルごとに処理します。

あるジャンルについて、再生時間の降順累積和を \(P\) とします。
このジャンルから \(t\) 曲選ぶと、得られる最大再生時間は \(P[t]\) です。

ただし、各ジャンルからは高々 \(L\) 曲までなので、

\[ 0 \leq t \leq \min(\text{そのジャンルの曲数}, L) \]

です。

DP の遷移は次のようになります。

\[ dp_{\text{new}}[j+t] = \max(dp_{\text{new}}[j+t], dp[j] + P[t]) \]

ここで、

• \(j\) はこれまでに選んだ曲数
• \(t\) は今回のジャンルから選ぶ曲数

です。

これを全ジャンルに対して行うと、固定した \(L\) に対する \(F[L]\) が求まります。

---

その後、偏りスコア \(x\) を \(1\) から順に試します。

各 \(x\) について、選ぶ曲数 \(s\) を \(1\) から \(M\) まで試します。

このとき必要なジャンルごとの上限は

\[ L = \left\lfloor \frac{x(s+1)}{x+1} \right\rfloor \]

です。

もし

\[ F[L][s] \geq K \]

なら、合計再生時間 \(K\) 秒以上の曲集合を選べて、かつ偏りスコアを \(x\) 以下にできます。

\(x\) を小さい順に調べているので、最初に条件を満たした \(x\) が答えです。

なお、すべての曲の再生時間合計が \(K\) 未満なら、そもそも条件を満たすプレイリストは作れないので、最初に \(-1\) を出力します。

計算量

\(M = 2N\) とします。

• 時間計算量: \(O(M^3) = O(N^3)\)
• 空間計算量: \(O(M^2) = O(N^2)\)

各 \(L\) について DP を行い、\(L\) は最大で \(M\) 通りあります。
固定した \(L\) に対する DP は \(O(M^2)\) でできるため、全体で \(O(M^3)\) です。

実装のポイント

• ジャンルごとに再生時間を降順ソートし、累積和を作ります。

• DP では不可能な状態を十分小さい値、例えば \(-10^{18}\) で初期化します。

• \(F[L][s]\) は「ちょうど \(s\) 曲選ぶ」ときの最大再生時間です。
  偏りスコア判定では \(s\) ごとに上限 \(L\) が変わるため、「ちょうど」で管理する必要があります。

• \(L\) が実際の最大ジャンル曲数を超える場合は、それ以上制限が緩くならないので、同じ DP 結果を使い回せます。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return

    N, K = data[0], data[1]
    M = 2 * N

    genres = [[] for _ in range(M + 1)]
    total = 0
    idx = 2
    for _ in range(M):
        b = data[idx]
        a = data[idx + 1]
        idx += 2
        genres[b].append(a)
        total += a

    if total < K:
        print(-1)
        return

    prefixes = []
    for arr in genres:
        if arr:
            arr.sort(reverse=True)
            p = [0] * (len(arr) + 1)
            s = 0
            for i, v in enumerate(arr, 1):
                s += v
                p[i] = s
            prefixes.append(p)

    prefixes.sort(key=len)

    max_cap = max(len(p) - 1 for p in prefixes)
    NEG = -10**18

    F = [None] * (M + 1)
    f0 = [NEG] * (M + 1)
    f0[0] = 0
    F[0] = f0

    for L in range(1, max_cap + 1):
        dp = [NEG] * (M + 1)
        dp[0] = 0
        max_s = 0

        for p in prefixes:
            c = len(p) - 1
            if c > L:
                c = L

            ndp = [NEG] * (M + 1)
            limit = max_s + 1
            ndp[:limit] = dp[:limit]

            dpl = dp
            ndpl = ndp

            for t in range(1, c + 1):
                add = p[t]
                j = t
                for s in range(limit):
                    v = dpl[s] + add
                    if v > ndpl[j]:
                        ndpl[j] = v
                    j += 1

            max_s += c
            dp = ndp

        F[L] = dp

    for L in range(max_cap + 1, M + 1):
        F[L] = F[max_cap]

    for x in range(1, M + 1):
        xp1 = x + 1
        for s in range(1, M + 1):
            cap = (x * (s + 1)) // xp1
            if F[cap][s] >= K:
                print(x)
                return

if __name__ == "__main__":
    main()

---

この解説は gpt-5.5-high によって生成されました。