個数制限がある場合の重複組合せの総数を動的計画法で求める

(2020-11-02)

個数制限がない場合

n種から制限なく重複を許してr個選ぶ組合せの総数nHrはn+r-1個の枠に入れるn-1個の種類を分ける区切りの場所の組合わせの総数と等しいので、 (n+r-1)C(n-1) = (n+r-1)Crで求められる。

3種から制限なく重複を許して4個選んだときの組合わせの総数

int factorial(int n)
{
    int x = 1;
    for (int i = n; i > 0; i--)
    {
        x *= i;
    }
    return x;
}

int H(int n, int r)
{
    // (n+r-1)Cr
    return factorial(n + r - 1) / (factorial(r) * factorial(n - 1));
}

個数制限がある場合

nHr

  • n種類目が少なくとも1つ選ばれる場合: nH(r-1) (それぞれの組み合わせにn種類目が1つ加わる)
  • n種類目が1つも選ばれない場合: (n-1)Hr (残りのn-1種類からr個選ぶ)

の和として表すこともでき、 漸化式 H(n, r) = H(n, r-1) + H(n-1, r) が成り立つ。

int H(int n, int r)
{
    if (n <= 0 || r < 0)
    {
        return 0;
    }
    if (n == 1 || r == 0)
    {
        return 1;
    }
    return H(n, r - 1) + H(n - 1, r);
}

n種類目が少なくとも1つ選ばれるということはn種類目から1 <= i <= r個選ばれ、n-1種類目までからr-i個選ばれると考えることもできるので、 合わせて H(n, r) = Σ(0 <= i <= r) H(n - 1, r-i) で求めることもでき、このループの条件を変えて H(n, r) = Σ(0 <= i <= stock[i]) H(n - 1, r-i) とすることで個数制限がある場合にも対応できる。 ただ動的計画法でH(n, r)の結果を再利用しても、ループを回す分計算量が増えてO(nr^2)になってしまう。

動的計画法(DP)で計算結果を再利用して計算量を減らす - sambaiz-net

ループの中身を分解すると

  • i = 0のとき: H(n - 1, r)
  • i > 0のとき: H(n - 1, r - 1) + H(n - 1, r - 2) + ... + H(n - 1, r - stocks[i]) = H(n, r - 1) - H(n - 1, r - stocks[i] - 1)

となるので H(n, r) = H(n - 1, r) + H(n, r - 1) - H(n-1, r - 1 - stocks[i]) に変形すると計算量をO(nr)に落とすことができる。

class Stock
{
public:
    Stock(vector<int> stocks);
    int H(int r);

private:
    vector<int> m_stocks;
    map<pair<int, int>, int> records;
    int H(int n, int r);
};

Stock::Stock(vector<int> stocks) { m_stocks = stocks; }

int Stock::H(int r)
{
    return H(m_stocks.size(), r);
}

int Stock::H(int n, int r)
{
    pair<int, int> key = {n, r};
    if (records.count(key) != 0)
    {
        return records[key];
    }

    if (n <= 0 || r < 0)
    {
        records[key] = 0;
        return 0;
    }
    if (r == 0)
    {
        records[key] = 1;
        return 1;
    }
    if (n == 1)
    {
        if (m_stocks[n - 1] < r)
        {
            return 0;
        }
        return 1;
    }
    int h = H(n, r - 1) + H(n - 1, r) - H(n - 1, r - m_stocks[n - 1] - 1);
    records[key] = h;
    return h;
}

参考

重複組合せ - Wikipedia

プログラミングコンテストチャレンジブック [第2版]