概要

\(2N\) 曲の候補から曲を選んで並べ、再生時間の合計が \(K\) 秒以上となるプレイリストを作るとき、同ジャンルの連続区間の最大長（偏りスコア）を最小化する問題です。

考察

重要な気づき：答えに対する二分探索

偏りスコア \(L\) を固定したとき、「\(L\) 以下のスコアで条件を達成できるか？」という判定問題に帰着できます。\(L\) が大きいほど制約が緩くなるため、答えに対して二分探索が適用できます。

判定問題の解き方

偏りスコアが \(L\) 以下となる条件は、どのジャンルも \(L\) 曲より多く連続しない配置が存在することです。

\(T\) 曲を並べたプレイリストで最大連続数を \(L\) 以下にする場合、各ジャンルから選べる曲数の上限 \(M\) は次の式で求まります：

\[M = \left\lfloor \frac{L \times (T+1)}{L+1} \right\rfloor\]

これは「\(L\) 曲並べたら 1 曲別ジャンルを挟む」というパターンから導かれます。例えば \(T=7, L=2\) なら、AA_AA_A のように配置でき、1ジャンルから最大 \(M = \lfloor 2 \times 8 / 3 \rfloor = 5\) 曲使えます。

貪欲法

\(T\) と \(M\) が決まれば、各ジャンルから再生時間の長い方から最大 \(M\) 曲まで候補に入れ、全候補の中から上位 \(T\) 曲を選んで合計が \(K\) 以上か確認すれば十分です（再生時間を最大化したいため）。

アルゴリズム

1. 全曲の合計が \(K\) 未満なら -1 を出力。
2. 各ジャンルの曲を再生時間の降順にソートしておく。
3. 答え \(L\) を二分探索する（範囲 \([1, 2N]\)）。
4. 判定関数 check(L):
   • \(T = 1, 2, \ldots, 2N\) について：
     • \(M = \lfloor L(T+1)/(L+1) \rfloor\) を計算
     • 各ジャンルから上位 \(\min(|genre|, M)\) 曲を候補に集める
     • 候補を降順ソートし、上位 \(T\) 曲の合計が \(K\) 以上なら true
5. check(L) が true となる最小の \(L\) を出力。

計算量

• 時間計算量: \(O(N^2 \log^2 N)\)
  • 二分探索: \(O(\log N)\) 回
  • 各判定: \(T\) を \(1\) ～ \(2N\) まで走査し、各回で \(O(N \log N)\) のソートと集計 → \(O(N^2 \log N)\)
• 空間計算量: \(O(N)\)

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

実装のポイント

• ジャンルごとに事前ソート: 各ジャンルの曲を再生時間の降順にソートしておくことで、判定時に上位 \(M\) 曲を即座に取得できます。

• \(M\) の計算式: \(\lfloor L(T+1)/(L+1) \rfloor\) は「\(T\) 曲の中で1ジャンルが占められる最大曲数」を正しく与えます。これは \((L+1)\) 曲ごとに少なくとも1曲は別ジャンルが必要、という制約から導かれます。

• 全 \(T\) を試す必要性: 曲数 \(T\) を固定しないと \(M\) が決まらないため、すべての \(T\) について試す必要があります。少ない曲数で \(K\) を達成できるケースもあるため、省略できません。

  ソースコード

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N;
    long long K;
    cin >> N >> K;
    
    int songs = 2 * N;
    vector<int> B(songs), A(songs);
    
    map<int, vector<int>> genre_map;
    long long total_sum = 0;
    
    for (int i = 0; i < songs; i++) {
        cin >> B[i] >> A[i];
        genre_map[B[i]].push_back(A[i]);
        total_sum += A[i];
    }
    
    if (total_sum < K) {
        cout << -1 << endl;
        return 0;
    }
    
    vector<vector<int>> genre_songs;
    for (auto& [g, v] : genre_map) {
        sort(v.begin(), v.end(), greater<int>());
        genre_songs.push_back(v);
    }
    
    int num_genres = genre_songs.size();
    
    auto check = [&](int L) -> bool {
        for (int T = 1; T <= songs; T++) {
            long long M = (long long)L * (T + 1) / (L + 1);
            
            vector<int> eligible;
            eligible.reserve(songs);
            
            for (int g = 0; g < num_genres; g++) {
                int take = min((long long)genre_songs[g].size(), M);
                for (int j = 0; j < take; j++) {
                    eligible.push_back(genre_songs[g][j]);
                }
            }
            
            if ((int)eligible.size() < T) continue;
            
            sort(eligible.begin(), eligible.end(), greater<int>());
            
            long long sum = 0;
            for (int i = 0; i < T; i++) {
                sum += eligible[i];
            }
            
            if (sum >= K) return true;
        }
        return false;
    };
    
    int lo = 1, hi = songs;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (check(mid)) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    
    cout << lo << endl;
    return 0;
}

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