ガジェット通信 GetNews

見たことのないものを見に行こう

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

DATE:
  • ガジェット通信 GetNewsを≫

問題のおさらい

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) には次のような関係があると分かります。

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

ここで「おや!」と気づかれたことでしょう。実は F(n, k) と G(n, k) は、まったく同じ漸化式を持つのです。n=k の場合に G(n, k) = 1 になる点も同じです。つまり、全ての n, k の組に対して、F(n, k) と G(n, k) の値は完全に等しいということなのです。したがって、解答のコードは次の通りです。上とほとんど同じものになります。

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

def g(n, k):
return f(n, k)

n, k = map(int, raw_input().split())
print f(n, k) + g(n, k)

片方を解くコードさえ書ければクリアできるということですね。もちろん、考え方によっては、F(n, k) と G(n, k) で異なる漸化式が得られることがあるでしょう。それでももちろん最終的な答えは一致します。それぞれを独立に解いて最終的な答えを得たとしても、まったく問題ありません。

なぜ2つの値は一致するのか?

さて、なぜ2つの値は一致するのでしょうか? もちろん、漸化式が一致するから、なんですが、もっと直感的な理解はできないでしょうか? そこで以下では、F(n, k) の分け方と G(n, k) の分け方とが実は1対1に対応づけられることを示します。

下図は、F(12, 5) の分け方の一つです。

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

この各グループを、多い順に縦に並べてみましょう。左の図です。そして各キャンディを四角に変えたのが真ん中の図です。そして、これを右図のように縦方向に見てみましょう。各縦列の四角の数をチョコレートの数と見なすわけです。すると、このときのチョコレートのグループの数はちょうど 5 個となることが分かります。

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

一列に並べたのが下図です。このように、題意を満たすキャンディの分け方とチョコレートの分け方とは、四角の並べ方を介して、ちょうど1対1で対応づけることができるのです。このことから両者の数が一致することが理解できます。

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

ちなみにこうした図は一般にヤング図形と呼ばれています。いろいろな数学の話題と関連する概念ですので、興味のある方は下記の記事などを参照してみてください。

参考:ヤング図形(Wikipedia)

みんなのコード

本問の挑戦者で、コードを公開して頂いた方のコードを Togetter でまとめました。(随時追加していきます。)こちらもぜひチェックしてください。

CodeIQ「キャンディ・アンド・チョコレート」問題 みんなのコード

CodeIQ運営事務局より

Kawazoeさん、ありがとうございました!
現在、Kawazoeさんの最新問題が出題中です。
ぜひ挑戦してみてくださいね!

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