概要

曲をいくつか選び、合計再生時間を \(K\) 秒以上にしたうえで、同じジャンルが連続する最大曲数を最小化します。

重要なのは、「並べ方による偏りスコア」は各ジャンルから何曲選んだかだけで決まり、曲の再生時間とは独立に考えられることです。

考察

ある選び方について、選んだ曲数をジャンルごとに数えます。

• 選んだ曲の総数を \(S\)
• あるジャンルから選んだ曲数の最大値を \(C\)

とします。

このとき、偏りスコアの最小値は

\[ \left\lceil \frac{C}{S-C+1} \right\rceil \]

になります。

なぜこの式になるか

最も多く選ばれているジャンルを考えます。その曲数は \(C\) 曲です。

それ以外の曲は \(S-C\) 曲あります。
これらを区切りとして使うと、最多ジャンルの曲を置ける場所は最大で

\[ S-C+1 \]

箇所あります。

例えば、他ジャンルの曲を x とすると、

_ x _ x _ x _

のように、前後と間に置ける場所があります。

最多ジャンルの \(C\) 曲をこの \(S-C+1\) 箇所にできるだけ均等に分けても、どこかには少なくとも

\[ \left\lceil \frac{C}{S-C+1} \right\rceil \]

曲が入ります。

したがって、偏りスコアはこれ未満にはできません。
また、実際にこの値を超えないように並べることができます。

よって、選んだ曲数の総数 \(S\) と、同じジャンルから選んだ最大曲数 \(C\) が分かれば、最小偏りスコアが計算できます。

---

次に、再生時間について考えます。

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

そのため、各ジャンルごとに曲を再生時間の降順にソートし、先頭から \(t\) 曲選んだときの合計を累積和で持ちます。

---

素朴に曲の部分集合を全探索すると、候補曲数は最大 \(2N=300\) なので、

\[ 2^{300} \]

通りになり到底間に合いません。

そこで、「各ジャンルから何曲選ぶか」だけに注目し、DP で合計再生時間の最大値を求めます。

アルゴリズム

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

1. ジャンルごとに曲をまとめる

各ジャンルについて、再生時間を降順に並べます。

例えば、あるジャンルに再生時間

\[ [10, 3, 8] \]

の曲があれば、降順にして

\[ [10, 8, 3] \]

とします。

そして累積和

\[ [0, 10, 18, 21] \]

を作ります。

これにより、そのジャンルから \(t\) 曲選ぶときの最大合計再生時間をすぐに取得できます。

---

2. 最大選択数 \(C\) を全探索する

\(C\) を「どのジャンルからも最大 \(C\) 曲までしか選ばない」という上限として考えます。

\(C=1,2,\dots,M\) について調べます。

---

3. DP で「合計 \(S\) 曲選んだときの最大再生時間」を求める

DP を次のように定義します。

\[ dp[s] = \text{これまで見たジャンルから合計 } s \text{ 曲選ぶときの最大再生時間} \]

各ジャンルについて、そのジャンルから \(t\) 曲選ぶ場合を遷移します。

ただし、今回の \(C\) に対して、各ジャンルから選べる曲数は最大 \(C\) 曲なので、

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

です。

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

\[ ndp[s+t] = \max(ndp[s+t], dp[s] + \text{prefix}[t]) \]

ここで \(\text{prefix}[t]\) は、そのジャンルから \(t\) 曲選んだときの最大合計再生時間です。

---

4. 条件を満たすなら偏りスコアを更新する

DP の結果、合計 \(S\) 曲選んで再生時間が \(K\) 以上になるなら、そのときの偏りスコアは

\[ \left\lceil \frac{C}{S-C+1} \right\rceil \]

です。

コードでは整数の切り上げを

\[ \frac{C + (S-C+1) - 1}{S-C+1} \]

として計算しています。

int denom = S - C + 1;
int score = (C + denom - 1) / denom;

これを答えの候補として最小値を更新します。

---

5. すべて選んでも \(K\) 未満なら -1

最初に全曲の再生時間合計を求めておきます。

もし全曲選んでも合計が \(K\) 未満なら、条件を満たすプレイリストは作れないので -1 を出力します。

計算量

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

ただし \(M=2N\) です。

\(N \leq 150\) なので、\(M \leq 300\) であり、十分高速に動作します。

実装のポイント

• 各ジャンル内では再生時間の長い順にソートします。

• 各ジャンルの累積和を作ることで、「そのジャンルから \(t\) 曲選ぶときの最大合計」を \(O(1)\) で得られます。

• DP 配列は毎回 \(-\infty\) で初期化します。

• 再生時間の合計や DP の値は大きくなる可能性があるので、long long を使います。

• 答えが \(1\) になった場合、それ以上小さくできないので探索を打ち切れます。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    long long K;
    cin >> N >> K;

    int M = 2 * N;
    vector<vector<int>> songs(M + 1);
    long long total = 0;

    for (int i = 0; i < M; i++) {
        int B, A;
        cin >> B >> A;
        songs[B].push_back(A);
        total += A;
    }

    if (total < K) {
        cout << -1 << '\n';
        return 0;
    }

    vector<vector<long long>> pref;
    for (auto &v : songs) {
        if (v.empty()) continue;
        sort(v.begin(), v.end(), greater<int>());
        vector<long long> p(v.size() + 1, 0);
        for (int i = 0; i < (int)v.size(); i++) {
            p[i + 1] = p[i] + v[i];
        }
        pref.push_back(move(p));
    }

    const long long NEG = -(1LL << 60);
    int ans = M;

    vector<long long> dp(M + 1), ndp(M + 1);

    for (int C = 1; C <= M; C++) {
        fill(dp.begin(), dp.end(), NEG);
        dp[0] = 0;
        int used = 0;

        for (const auto &p : pref) {
            int len = (int)p.size() - 1;
            int lim = min(len, C);

            fill(ndp.begin(), ndp.end(), NEG);

            for (int s = 0; s <= used; s++) {
                if (dp[s] == NEG) continue;
                for (int t = 0; t <= lim; t++) {
                    ndp[s + t] = max(ndp[s + t], dp[s] + p[t]);
                }
            }

            used += lim;
            dp.swap(ndp);
        }

        for (int S = C; S <= used; S++) {
            if (dp[S] >= K) {
                int denom = S - C + 1;
                int score = (C + denom - 1) / denom;
                ans = min(ans, score);
            }
        }

        if (ans == 1) break;
    }

    cout << ans << '\n';
    return 0;
}

---

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