同種のものを区別せずにM個選ぶ組み合わせーARC028D 注文の多い高橋商店(前編)

プログラミング
Sponsored

この記事ではAtCoderというサイトの問題を参考に、「同種のものを区別せずにM個選ぶ組み合わせ」について解説する。

問題:ARC028 D - 注文の多い高橋商店

D - 注文の多い高橋商店
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

この問題では、「同種のものを区別せずにM個選ぶ組み合わせ」と「戻す動的計画法(DP)」についての考察が必要となる。「戻すDP」の解説は次回

で行うこととして、ここでは「同種のものを区別せずにM個選ぶ組み合わせ」について考えよう。これに該当する問題文は、以下の部分である。

高橋商店では \(N\) 種類の商品が売られています。「どの種類の商品がいくつあるか」の情報が与えられるので、「合計 \(M\) 個の商品を選ぶ方法」の数を求めてください。ただし、同じ種類の商品は区別しないこととします。

解説

考え方

この形式の問題では、 \({}_n \mathrm{ C }_k\) などを使って各通りの組み合わせを個別に考えるのは困難である。よってここでは、とある小さな個数の組み合わせの数を用いて、それより少しだけ大きい個数の組み合わせがどのように表せるかについて考える。すなわち、漸化式的な考え方を用いる。

例として、商品 \(A\) が \(4\) 個、 \(B\) が \(2\) 個、 \(C\) が \(3\) 個の場合について考えよう。

具体例

このとき、 \(A,B\) から \(1\) 個選ぶ方法は、 \(\{A, B\}\) の \(2\) 通りである。同様に、 \(A,B\) のみから \(2\) 個選ぶ方法は、 \(\{AA, AB, BB\}\) の \(3\) 通り、 \(3\) 個選ぶ方法も \(\{AAA, AAB, ABB\}\) の \(3\) 通りである。また、 \(A,B,C\) から \(3\) 個選ぶ方法は、 \(\{AAA, AAB, AAC, ABB, ABC, ACC, BBC, BCC, CCC\}\) の \(9\) 通りである。これらにはどのような数的関係があるだろうか?

ここで、それぞれの組み合わせを次のように並べてみよう。

上図の \((a)\) と \((b)\) を比較すると、 \(A,B,C\) から \(3\) 個選ぶ組み合わせは、 \(A,B\) から \(0\) ~ \(3\) 個選ぶ組み合わせの空いたスペースに \(C\) を詰め込んだものとして考えることができる。したがって、 \(A,B\) から \(0\) 個選ぶ組み合わせの数を \(1\) とし、 \(n\) 番目の商品までの中から \(m\) 個選ぶ組み合わせの数を \(b_{n,m}\) とおくと、それぞれの数量には

という関係があることがわかる。

次に、同様の方法で \(A,B,C\) から \(4\) 個選ぶ方法と \(5\) 個選ぶ方法について考えてみる。

今回も空いたスペースに \(C\) を詰め込めばよいのだが、 \(C\) は \(3\) 個しかないため、 \(A,B,C\) から \(4\) 個選ぶ( \(b_{3,4}\) を求める)場合は \(b_{2,0}\) 個、 \(5\) 個選ぶ( \(b_{3,5}\) を求める)場合は \(b_{2,0}+b_{2,1}\) 個が組み合わせを形成する条件から外れる。よって、 \(n\) 番目の商品の個数を \(a_{n}\) とおき、以上のことを一般化すると、次のように表せる。

\(m<=a_{n}\) のとき

$$b_{n,m} = \sum_{k=0}^{M}b_{n-1,k}$$

\(m>a_{n}\) のとき

$$b_{n,m} = \sum_{k=0}^{m}b_{n-1,k}-\sum_{k=0}^{m-a_{n}-1}b_{n-1,k}$$

動的計画法(DP)による計算

以上のルールにしたがって、「 \(n\) 種類の商品の中から、同種の商品を区別せずに、 \(m\) 個選ぶ組み合わせ」を表に示すと以下のようになる。

すなわち、例えば \(A, B\) の \(2\) 種類の商品から \(3\) 個選ぶ組み合わせは \(3\) 通り、 \(A, B, C\) の \(3\) 種類の商品から \(5\) 個選ぶ組み合わせは \(11\) 通りであることが読み取れる。このように、それぞれの数的関係を漸化式的に捉え、表を順次埋めていくアルゴリズムを動的計画法DP)という。

次回予告

ここまで、「同種のものを区別せずにM個選ぶ組み合わせ」について解説し、それを実装するためのアルゴリズムについても触れたが、この問題にはまだ続きがある。問題文の後半では、最後に説明した動的計画法の応用である「戻すDP」についての知識が要求される。

この「戻すDP」の解説と問題に対するC++での解答は、後編

で行う。

Comments