C++で解く「音楽プレイリストの総数」問題 ― 動的計画法による実装ガイド

問題の概要

N種類の異なる楽曲を収めたミュージックプレイヤーがあり、旅行中に合計L曲を聴きたいと考えます。このとき、次の条件をすべて満たすプレイリストを作成する必要があります。

• すべての楽曲が少なくとも1回は再生されること
• ある楽曲をもう一度再生できるのは、その後にK曲以上の他の楽曲が再生されてからであること

この条件を満たすプレイリストの総数を求めます。答えは非常に大きな値になる可能性があるため、10⁹ + 7 で割った余りを返します。

たとえば、入力が N = 2、L = 3、K = 0 の場合、出力は 6 となります。これは [1,1,2]、[1,2,1]、[2,1,1]、[2,2,1]、[2,1,2]、[1,2,2] の6通りが存在するためです。

解法のアプローチ：動的計画法（DP）

この問題は動的計画法を用いて効率的に解くことができます。dp[i][j] を「i曲目まで聴いた時点で、ちょうどj種類の楽曲を使用しているプレイリストの数」と定義すると、状態遷移は次の2通りに分けられます。

• 新しい楽曲を追加する場合： まだ使っていない曲は N − (j − 1) 曲あるので、dp[i−1][j−1] × (N − (j−1)) 通り
• 既存の楽曲を繰り返す場合（j > K のとき）： 直近K曲以内に再生した曲は選べないため、残りの j − K 曲から選択でき、dp[i−1][j] × (j − K) 通り

オーバーフローを防ぐため、剰余演算を安全に行うヘルパー関数を用意しておきます。

• 関数 add(a, b)：((a mod m) + (b mod m)) mod m を返す
• 関数 sub(a, b)：((a mod m) − (b mod m) + m) mod m を返す
• 関数 mul(a, b)：((a mod m) × (b mod m)) mod m を返す

メイン処理の流れは以下のとおりです。

• サイズ (L + 1) × (N + 1) の2次元配列 dp を作成する
• dp[0][0] := 1 と初期化する
• i を 1 から L まで、j を 1 から N まで二重ループで回し、上記の漸化式に従って dp[i][j] を更新する
• 最終的に dp[L][N] を返す

C++での実装例

以下のコードで実際の実装を確認できます。

#include <bits/stdc++.h>
using namespace std;
const int m = 1e9 + 7;
typedef long long int lli;
class Solution {
   public:
   int add(lli a, lli b){
      return ((a % m) + (b % m)) % m;
   }
   int sub(lli a, lli b){
      return ((a % m) - (b % m) + m) % m;
   }
   int mul(lli a, lli b){
      return ((a % m) * (b % m)) % m;
   }
   int numMusicPlaylists(int N, int L, int K) {
      vector < vector <int> > dp(L + 1, vector <int>(N + 1));
      dp[0][0] = 1;
      for(int i = 1; i <= L; i++){
         for(int j = 1; j <= N; j++){
            dp[i][j] = mul(dp[i - 1][j - 1], (N - (j - 1)));
            if(j > K){
               dp[i][j] = add(dp[i][j], mul(dp[i - 1][j], j - K));
            }
         }
      }
      return dp[L][N];
   }
};
main(){
   Solution ob;
   cout << (ob.numMusicPlaylists(2, 3, 0));
}

入力

2, 3, 0

出力

6

まとめ

本記事では、「全曲を最低1回再生し、同じ曲の再再生にはK曲の間隔が必要」という制約下でのプレイリストの総数を、動的計画法によって求める方法を紹介しました。時間計算量は O(L × N)、空間計算量も O(L × N) となり、制約の多いカウント問題に対するDPの典型的な適用例として学び価値の高いテーマです。