C++で最も視聴された上位k番組の合計視聴時間を求める方法

テレビ番組のリストと、それぞれの視聴時間のリスト、さらに整数 k が与えられたとします。shows[i] と duration[i] は、i 番目の人が視聴した番組名とその視聴時間を表しています。このとき、最も視聴時間の長い上位 k 個の番組の合計視聴時間を求めるのが本記事の目的です。

問題の例

例えば、入力が以下のような場合を考えてみましょう。

• shows: ["Castle Play", "Fairy Tale Series", "Castle Play", "Jerry Mouse", "Rich Boy"]
• duration: [6, 4, 6, 14, 5]
• k = 2

この場合の出力は 26 になります。

理由を見てみると、「Castle Play」は2回登場するため合計視聴時間は 6 + 6 = 12 分、「Jerry Mouse」は 14 分です。これら上位2番組の合計は 12 + 14 = 26 となるため、答えは 26 になります。

解決のためのアルゴリズム

この問題は、以下の手順で解くことができます。

1. map<string, int> 型のマップ m を定義します。
2. n := ベクトル v のサイズとします。
3. i を 0 から n-1 までループし、m[v[i]] += d[i] として各番組の視聴時間を累積します。
4. 配列 arr を定義します。
5. マップ m の各キーと値のペアに対して、値(合計視聴時間)を arr の末尾に追加します。
6. arr を降順にソートします。
7. ret := 0 と初期化します。
8. i を 0 から k-1 までループし、ret += arr[i] として上位 k 件の視聴時間を合計します。
9. ret を返します。

C++での実装例

理解を深めるために、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int solve(vector<string>& v, vector<int>& d, int k) {
        map <string, int> m;
        int n = v.size();
        for(int i = 0; i < n; i++){
            m[v[i]] += d[i];
        }
        vector < int > arr;
        for(auto it : m){
            arr.push_back(it.second);
        }
        sort(arr.rbegin(), arr.rend());
        int ret = 0;
        for(int i = 0; i < k; i++){
            ret += arr[i];
        }
        return ret;
    }
};
int main(){
    vector<string> v = {"Castle Play", "Fairy Tale Series", "Castle
    Play", "Jerry Mouse", "Rich Boy"};
    vector<int> v1 = {6, 4, 6, 14, 5};
    Solution ob;
    cout << (ob.solve(v, v1, 2));
}

入力

{"Castle Play", "Fairy Tale Series", "Castle Play", "Jerry Mouse",
"Rich Boy"}, {6, 4, 6, 14, 5}, 2

出力

26

コードのポイント解説

この実装では、まず std::map を使って同じ番組名の視聴時間を自動的に集計しています。map のキーは番組名、値は累積視聴時間です。

次に、集計結果を vector に取り出し、rbegin() と rend() を使った降順ソートを行うことで、視聴時間の長い順に並べ替えています。

最後に先頭から k 件分を足し合わせるだけで、求めたい合計視聴時間が得られます。計算量は O(n log n)(ソート部分が支配的)であり、非常にシンプルかつ効率的なアプローチです。