C++で解く「オールインワン」問題：OTTサービス契約の最小費用を求めるアルゴリズム

問題概要

ある通信事業者が「オールインワン」というサービスを導入したとします。このサービスは、n社のOTTコンテンツプロバイダすべてにアクセスできるようになり、固定料金はkドルです。一方、各OTTプラットフォームに直接契約する場合は、それぞれ個別の料金を支払う必要があります。

しかし、毎月すべてのプラットフォームが必要になるとは限りません。そこで、必要な期間だけ賢くサービスを利用し、コストを最小限に抑える方法を考えることになります。プラットフォームiの利用開始月は配列 start_month に、利用終了月は配列 end_month に格納されています。また、各プラットフォームの契約料金は配列 price[i] で与えられます。求めるのは、必要な期間に応じてすべてのサービスを利用するために支払うべき最小金額です。

入力例

n = 3、k = 10、start_month = {1, 2, 1}、end_month = {3, 3, 2}、price = {5, 7, 8} の場合、出力は 30 になります。

計算の内訳

このケースでは、合計3か月間サービスの契約が必要です。

• 1か月目： プラットフォーム1と3の契約が必要です。個別に契約すると 5 + 8 = 13ドルですが、「オールインワン」なら10ドルで済みます。
• 2か月目： 3つすべてのプラットフォームが必要です。個別契約では合計20ドルになりますが、「オールインワン」なら10ドルです。
• 3か月目： 個別契約の合計は12ドルですが、やはり10ドルでカバーできます。

したがって、合計費用は 10 + 10 + 10 = 30ドル となります。

解法のアプローチ（スイープライン法）

この問題は、イベントごとに区間を処理していく「スイープライン（走査線）」的な考え方で効率よく解けます。手順は以下の通りです。

1. (開始月, 料金) と (終了月+1, -料金) のペアを配列に登録します。終了月に+1するのは、その月から契約が不要になるためです。
2. ペアの配列をソートします。
3. 各イベントを順に処理し、前回のイベントからの期間に対して「個別契約の合計額c」と「定額k」の小さい方を掛けて答えに加算します。
4. イベント処理時に現在の契約額cを更新していきます。

pairArray を宣言する
i := 0 から i < n まで i を1ずつ増やしながら繰り返す:
    pairArray の末尾に (start_month[i], price[i]) を挿入
    pairArray の末尾に (end_month[i] + 1, -price[i]) を挿入
pairArray をソートする
pre := 0
c := 0
res := 0
pairArray の各要素 p について:
    day := p の第1要素 - pre
    res := res + min(k, c) * day
    c := c + p の第2要素
    pre := p の第1要素
res を返す

C++による実装例

以下に実際の実装を示します。

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

int solve(int n, int k, int start_month[], int end_month[], int price[]){
   vector<pair<int, int>> pairArray;
   for(int i = 0; i < n; i++) {
      pairArray.push_back(make_pair(start_month[i], price[i]));
      pairArray.push_back(make_pair(end_month[i] + 1, -price[i]));
   }
   sort(pairArray.begin(), pairArray.end());
   int pre = 0;
   int c = 0;
   int res = 0;
   for(auto p : pairArray) {
      int day = p.first - pre;
      res += min(k, c) * day;
      c += p.second;
      pre = p.first;
   }
   return res;
}
int main() {
   int n = 3, k = 10, start_month[] = {1, 2, 1}, end_month[] = {3, 3, 2}, price[] = {5, 7, 8};
   cout<< solve(n, k, start_month, end_month, price);
   return 0;
}

入力

3, 10, {1, 2, 1}, {3, 3, 2}, {5, 7, 8}

出力

30

まとめ

このアルゴリズムの計算量は、ペアの作成にO(n)、ソートにO(n log n)かかるため、全体としてO(n log n)です。各区間で「個別契約の合計」と「定額プラン」の安い方を選ぶことで、常に最適な支払いを実現できます。サブスクリプションのコスト最適化など、実務でも応用範囲の広いテクニックなので、ぜひマスターしておきましょう。