Rustコトハジメ

プログラミング言語Rustに関する情報をお届けします。

分割数の漸化式の考え方

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

蟻本の分割数のところで3時間くらいフリーズしていた。

分割数というのは、n個のボールがあった時にこれらをm個以下の箱に入れる方法は何通りありますか?ということ。例えば、nが6個でmが3の場合は、(1,1,4),(1,2,3),(2,2,2),(1,5),(2,4),(3,3),(6)の7通りがある。これをP(n,m)と書く。

P(n,m)=P(n,m-1)+P(n-m,m)の考え方

蟻本では、いきなり、P(n,m)=P(n,m-1)+P(n-m,m)という漸化式が出てくるが、ネットで調べると、これを理解するのに数日かかったという人もいるくらい、難しい。これが初級と言われると困る。

だけど調べてみると非常にわかりやすい記事を見つけた。

techtipshoge.blogspot.com

何を言ってるかというと、

  1. P(n,m)=P(n,m-1)+(nをジャストm個に分割する方法)は定義そのもの
  2. 後者がP(n-m,m)に等しいことがわかればいい
  3. 各箱には1つは入れないといけないという制約があるのだから、それは後で加えるということにしてひとまず取り除いたら、P(n-m,m)だよね

ということ。

3について、例えばP(6,3)の場合は、P(n-m,m)はP(3,3)になるけど、これはあとで1を加えることを前提にすると(1,1,1),(1,2,0),(3,0,0)と考えることが出来て、結果として(2,2,2),(2,3,1),(4,1,1)が得られる。前者のP(n,m-1)の方はP(6,2)だから、(6),(5,1),(4,2),(3,3)となる。

ちなみに、誤った漸化式として挙げられてるP(n,m)=sum_k P(n-k,m-1)は、最初にk取った場合の計算のkについての和と考えると確率DPみたいな形をしているし、逆に、上と同じように、最初にk個取り除いて最後の1箱に入れることを約束すると考え方も出来るのが興味深かった。