SRM 679 Div2 Easy: ListeningSongs

競技プログラミング

問題

TopCoder Statistics - Problem Statement

2 つの音楽アルバム A, B について、曲の長さ(d1, d2)が与えられる(秒)。 曲の長さの合計が上限 minutes を超えないように各アルバムから曲を選ぶとき、選べる曲数の最大値を返す。 ただし、各アルバムからそれぞれ最低 T 曲選ばなければならない(A から T 曲, B から T 曲)。このような選び方がない場合は -1 を返す。

解法

結果が -1 の時の条件に注意してそのまま書く。d1, d2 をソートして先頭から T 個足したあと、新しい配列に足してない要素を突っ込んでソート、先頭から上限時間を超えないように選んでいくような処理を書いた。

class ListeningSongs {
    public:
    int listen(vector<int> d1, vector<int> d2, int minutes, int T) {
        int n = d1.size();
        int m = d2.size();
        if(T > n or T > m) return -1;
        int time = minutes * 60;
        sort(d1.begin(), d1.end());
        sort(d2.begin(), d2.end());
        int tot = 0;
        for(int i=0; i<T; i++) tot += d1[i] + d2[i];
        if(tot > time) return -1;

        vector<int> v;
        for(int i=T; i<n; i++) v.push_back(d1[i]);
        for(int i=T; i<m; i++) v.push_back(d2[i]);
        sort(v.begin(), v.end());

        int ans = 2 * T;
        for(int i=0; i<(int)v.size(); i++) {
            tot += v[i];
            if(tot <= time)
                ans++;
            else
                break;
        }

        return ans;
    }
};

結果

Rating: 463 -> 536(+73)

初めてレートが上昇した。問題把握に時間が掛かり過ぎて 50 分くらいで提出した気がする（103 point）。同じ部屋の人はかなり落ちてた。