概要

\(2N\) 曲の中から合計再生時間が \(K\) 秒以上になるように曲を選び、それらを並べたときに同じジャンルが連続する最大個数（偏りスコア）を最小化する問題です。 条件を満たす曲の選び方と並べ方のうち、最小の偏りスコアを求めます。

考察

1. 偏りスコア \(X\) の条件

ある \(M\) 曲を選んだとき、特定のジャンル \(g\) に属する曲数を \(n_g\) とします。この \(M\) 曲をうまく並べて偏りスコアを \(X\) 以下にできる条件を考えます。

ジャンル \(g\) 以外の曲数は \(M - n_g\) です。これらを「仕切り」として使うと、ジャンル \(g\) の曲を置ける場所は、仕切りの前後と間の合計 \((M - n_g + 1)\) 箇所あります。 各箇所に最大 \(X\) 個までジャンル \(g\) の曲を置けるため、以下の不等式が成り立てば偏りスコアを \(X\) 以下に抑えられます。 $\(n_g \leq X \times (M - n_g + 1)\)$

これを \(n_g\) について解くと： $\(n_g \leq \frac{X(M+1)}{X+1}\)\( 曲数は整数なので、\)n_g \leq \lfloor \frac{X(M+1)}{X+1} \rfloor\( となります。つまり、**どのジャンルからも最大 \)C = \lfloor \frac{X(M+1)}{X+1} \rfloor$ 曲までしか選べない**という制約に言い換えられます。

2. 答えの二分探索

偏りスコア \(X\) が小さければ小さいほど条件は厳しくなり、大きければ緩くなります。この単調性を利用して、最小の \(X\) を二分探索で求めます。

3. 判定関数の設計（貪欲法）

固定された \(X\) に対して、条件を満たす曲の選び方があるかを判定します。 選ぶ曲数 \(M\) を \(1\) から \(2N\) まで全通り試します。各 \(M\) について、合計再生時間を最大化するには以下の戦略が有効です。 1. 各ジャンル内で、再生時間が長い順に曲を並べておく。 2. 全曲の中から、「そのジャンル内で \(C\) 番目以内」の曲だけを候補とする。 3. 候補の中から再生時間が大きい順に \(M\) 曲選び、その合計が \(K\) 以上になるかを確認する。

アルゴリズム

1. 前処理:
   • 曲をジャンルごとにグループ化し、各ジャンル内で再生時間の降順にソートします。
   • 全ての曲に対し、「そのジャンル内で何番目に長い曲か（ランク）」を記録します。
2. 二分探索:
   • 範囲 \([1, 2N]\) で偏りスコア \(X\) を二分探索します。
3. 判定関数 check(X):
   • \(M = 1\) から \(2N\) までループします。
   • 各 \(M\) に対し、各ジャンルから選べる上限数 \(C = \lfloor \frac{X(M+1)}{X+1} \rfloor\) を計算します。
   • ジャンル内ランクが \(C\) 以下の曲を再生時間の降順に \(M\) 個選び、合計が \(K\) 以上なら true を返します。
4. 出力:
   • 二分探索で見つかった最小の \(X\) を出力します。一度も条件を満たさなければ \(-1\) を出力します。

計算量

• 時間計算量: \(O(N^2 \log N)\)
  • 曲のソート: \(O(N \log N)\)
  • 二分探索の回数: \(O(\log N)\)
  • 判定関数: \(M\) のループ (\(2N\) 回) \(\times\) 曲の走査 (\(2N\) 回) = \(O(N^2)\)
  • 全体で \(O(N^2 \log N)\) となり、\(N=150\) では十分に高速です。
• 空間計算量: \(O(N)\)
  • 曲の情報を保持するリストなどに使用します。

実装のポイント

• ソートの工夫: 判定関数の中で毎回ソートすると遅くなる可能性があるため、あらかじめ全曲を「再生時間の降順」でソートしておき、判定関数内ではランクの比較だけで \(M\) 曲選ぶようにすると効率的です。

• \(M\) 曲選べない場合: \(C\) の制限によって合計で \(M\) 曲選べない場合は、その \(M\) については条件不適としてスキップします。

• \(C=0\) のケア: \(X\) や \(M\) が小さいときに \(C=0\) になる場合があります。この場合、そのジャンルからは 1 曲も選べません。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * Problem Analysis:
 * We need to find the minimum bias score X such that we can select M songs (1 <= M <= 2N)
 * with a total duration >= K and arrange them so that no more than X consecutive songs
 * are of the same genre.
 * 
 * The condition for an arrangement of M songs to have a bias score of at most X is that
 * for each genre g, the number of songs selected from that genre, n_g, must satisfy:
 * n_g <= X * (M - n_g + 1)
 * This simplifies to:
 * n_g * (X + 1) <= X * (M + 1)
 * n_g <= floor(X * (M + 1) / (X + 1))
 * 
 * To maximize the total duration for a fixed bias score X and total song count M, 
 * we should pick the M largest duration songs across all genres, with the restriction 
 * that we can pick at most C = floor(X * (M + 1) / (X + 1)) songs from each genre.
 */

struct Song {
    int duration;
    int rank; // rank of the song within its genre (1-indexed, largest duration is rank 1)
};

int main() {
    // Optimize I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    long long K;
    if (!(cin >> N >> K)) return 0;

    // Group songs by genre
    vector<vector<int>> genre_songs(2 * N + 1);
    for (int i = 0; i < 2 * N; ++i) {
        int b, a;
        cin >> b >> a;
        if (b >= 1 && b <= 2 * N) {
            genre_songs[b].push_back(a);
        }
    }

    // Sort songs within each genre and store them with their genre-rank
    vector<Song> all_songs;
    for (int i = 1; i <= 2 * N; ++i) {
        if (genre_songs[i].empty()) continue;
        sort(genre_songs[i].rbegin(), genre_songs[i].rend());
        for (int j = 0; j < (int)genre_songs[i].size(); ++j) {
            all_songs.push_back({genre_songs[i][j], j + 1});
        }
    }

    // Sort all songs by duration in descending order
    sort(all_songs.begin(), all_songs.end(), [](const Song& a, const Song& b) {
        if (a.duration != b.duration) return a.duration > b.duration;
        return a.rank < b.rank;
    });

    // Check if a bias score X is achievable
    auto check = [&](int X) {
        for (int M = 1; M <= 2 * N; ++M) {
            // Maximum songs allowed per genre for this M and X
            long long C = (long long)X * (M + 1) / (X + 1);
            if (C == 0) continue; 

            long long current_sum = 0;
            int count = 0;
            // Greedily pick the M best available songs
            for (const auto& song : all_songs) {
                if (song.rank <= C) {
                    current_sum += (long long)song.duration;
                    count++;
                    if (count == M) break;
                }
            }
            // If we found exactly M songs and their sum is >= K, X is achievable
            if (count == M && current_sum >= K) return true;
        }
        return false;
    };

    // Binary search for the minimum achievable bias score X
    int low = 1, high = 2 * N;
    int ans = -1;

    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (check(mid)) {
            ans = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    cout << ans << endl;

    return 0;
}

この解説は gemini-3-flash-thinking によって生成されました。