体験を伝える―『ガジェット通信』の考え方

面白いものを探しにいこう 本物を体験し体感しよう 会いたい人に会いに行こう 見たことのないものを見に行こう そしてそれをやわらかくみんなに伝えよう [→ガジェ通についてもっと詳しく] [→ガジェット通信フロアについて]

数学の問題をプログラミングで解こう!「キャンディ・アンド・チョコレート」問題解説

問題のおさらい

n 個のキャンディをグループに分けます。
グループの最大のキャンディの個数が k 個となるような分け方の数を F(n, k) と定義します。

例えば、F(8, 3)=5 です。このときの分け方を以下に示します。
なお個々のキャンディを区別せずに扱う点に注意してください。

数学の問題をプログラミングで解こう!「キャンディ・アンド・チョコレート」問題解説

同様に、F(4, 2)=2,F(20, 6)=90 となることが確かめられます。

次に、n 個のチョコレートをグループに分けます。
グループの数がちょうど k 個となるような分け方の数を G(n, k) と定義します。

例えば、G(9, 4)=6 です。このときの分け方を以下に示します。

数学の問題をプログラミングで解こう!「キャンディ・アンド・チョコレート」問題解説

同様に、G(4, 2)=2,G(18, 4)=47 となることが確かめられます。

標準入力から、自然数 n と k (1 ≦ k ≦ n ≦ 100)が半角空白区切りで与えられます。
標準出力に F(n, k)+G(n, k) の値を出力するプログラムを書いてください。

例えば入力が「4 2」の場合は、F(4, 2)+G(4, 2) の値である「4」を出力してください。

方針

キャンディとチョコレートをグループ分けする問題です。ぱっと見て、「2つの問題を解かないといけないの?」と思われたかもしれません。たしかに一見したところ、キャンディとチョコレートで別の問題のように見えます。しかし、実は2つには非常に深い関連があります。一つ一つ見ていきましょう。

キャンディの方からです。これまでに何度も登場している「一つ前の状態に着目しよう」という考え方はここでも有効です。

F(n, k) とは、グループの中の最大のキャンディの個数が k 個となるような分け方の数のことでした。いま、そのような分け方において、最大のグループを取り除いてみましょう。残るキャンディは n-k 個です。そしてこの残りの部分では、グループの最大のキャンディの個数は k 個以下です。k 個以下というのは、ちょうど 1 個、 2 個、3 個、…、k 個のどれかだということですね。したがって、F(n, k) には次のような関係があることが分かります。

数学の問題をプログラミングで解こう!「キャンディ・アンド・チョコレート」問題解説

漸化式ができてしまえば、再帰のコードが有効です。n=k の場合に F(n, k) の値は 1 になる点に気を付ければコードが書けそうです。ただ、単純な再帰コードだと処理量が非常に多くなってしまうので、前回(数学の問題をプログラミングで解こう!「ウッド・キーパー」問題解説)と同じく、メモ化再帰のコードで解くことができます。

コード例(Python)は以下です。

d = dict()

def f(n, k):
if n < k: return 0
if n == k: return 1
if d.has_key((n, k)): return d[(n, k)]
a = 0
for s in range(1, k+1):
a += f(n-k, s)
d[(n, k)] = a
return a

さて、次に G(n, k) の方です。F(n, k) と同様、一つ前の状態に着目することがポイントです。

G(n, k) とは、グループの数がちょうど k 個となる分け方の数のことでした。いま、そのような分け方において、各グループからチョコレートを 1 個ずつ取り除いたとしてみましょう。残るチョコレートは n-k 個です。そしてこの残りの部分から、チョコレートが 0 個になったグループを消してみます。すると残りのグループの数は k 個以下のどれかです。このことから、G(n, k) には次のような関係があると分かります。

1 2次のページ
CodeIQ MAGAZINEの記事一覧をみる
  • 誤字を発見した方はこちらからご連絡ください。
  • ガジェット通信編集部への情報提供はこちらから
  • 記事内の筆者見解は明示のない限りガジェット通信を代表するものではありません。