Search on the blog

2011年1月28日金曜日

分割数を考える

『プログラミングコンテストチャレンジブック』で挑戦した問題。

n個の互いに区別できない商品を、m個以下に分割するパターンの総数を求めよ。

一般に、m=nのとき、このパターン数をnの分割数と呼ぶらしい。

悩んで、悩んで2つ日目に分かった。(解説が天才的すぎて凡人の僕にはちょっと理解できません。。)
以下、凡人でも分かりそうな解説。
まず、dp[i][j]を整数jをi個以下に分割するパターン数とする。
jをi個以下に分割するパターンは、jをi-1個以下に分割するパターンとjをi個に分割するパターンの和である。ここで、前者の「jをi-1個に分割するパターン」はdp[i-1][j]と書ける。

次に後者。「jをi個に分割するパターン」は、予めi個を1個ずつi個の集合に割り当てて、残ったj-i個をこの集合に割り当てるパターンを考えればいいと分かる。
ちょっと、ややこしいので例題を。
10個を4個に分けるパターンは、まず集合が4ついるので、それぞれの集合に1個ずつ割り当てる。
1, 1, 1, 1
あとは、残った6個をこの4つの集合に割り振るパターン数を考えればよい。
例えば、
6, 0, 0, 0
1, 1, 1, 3
2, 2, 0, 2
などが考えられる。
これを、予め作っておいた集合
1, 1, 1, 1に加えれば4つに分割するパターンが出来ることがわかる。よって、「jをi個に分割するパターン」は、dp[i][j-i]と書ける。

以上の議論から、
dp[i][j] = dp[i-1][j] + dp[i][j-i]
という漸化式が得られる。これはDPを使えば、O(n*m)で解けます。

ソースは、・・・・・

ソースを見たい人は、この本を買おう!(笑)

2 件のコメント:

  1. こんばんは、この本を最近読んでいるものです。
    この問題の解説がよく分からず、ぐぐった所こちらのサイトがヒットしました。
    説明、わかり易かったです!

    返信削除
  2. この本を読んでいて、この問題で休日丸一日悩まされていたのですがこのサイトを拝見させていただき理解することができました!
    本当にありがとうございました。

    返信削除