CodeIQ MAGAZINECodeIQ MAGAZINE

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

2017.08.17 Category:CodeIQ問題解説・リーダーボード Tag: ,

  • 5
  • このエントリーをはてなブックマークに追加
riverplus

「数学の問題をプログラミングで解こう!」シリーズ。
お菓子をグループ分けする問題でした。
一見、2つの独立した問題ですが、実は2つに興味深いつながりがあります。

みなさんはうまくできましたか?
ぜひ出題者のKawazoeさんによる本記事で解法をチェックしてください!
by CodeIQ運営事務局

問題のおさらい

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 となることが確かめられます。

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

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

方針

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

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

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

漸化式ができてしまえば、再帰のコードが有効です。nk の場合に 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 個ずつ取り除いたとしてみましょう。残るチョコレートは nk 個です。そしてこの残りの部分から、チョコレートが 0 個になったグループを消してみます。すると残りのグループの数は k 個以下のどれかです。このことから、G(n, k) には次のような関係があると分かります。

ここで「おや!」と気づかれたことでしょう。実は F(n, k) と G(n, k) は、まったく同じ漸化式を持つのです。nk の場合に 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さんの最新問題が出題中です。
ぜひ挑戦してみてくださいね!

  • 5
  • このエントリーをはてなブックマークに追加

■関連記事

【コードミステリ】数字に隠されたメッセージ【言語不問】解答と解説... 【コードミステリ】数字に隠されたメッセージ【言語不問】 本問題は、表題のテーマで、簡単なプログラムを書くものです。 喜屋武ちあきさんによるCodeIQ MAGAZINEでのブックレビューに合わせて、『顔貌売人』(文藝春秋)とのコラボ問題として出題されたものです。 それでは以下、問題とその解...
数学の問題をプログラミングで解こう!「ディバイド・アウト」問題解説... 問題のおさらい 自然数 n と素数 p に対し、n の階乗(n!)を p でこれ以上割り切れなくなるまで繰り返し割り、その商をさらに p で割ったときの余りを F(n, p) と定義します。 例えば F(12, 5)=4 です。 12!(=479001600)は 5 で最大 2 回割ることができ...
【息抜き】ファイル名を作ろう【言語不問】解答と解説... 【息抜き】ファイル名を作ろう【言語不問】 本問題は、表題のテーマで、簡単なプログラムを書くものです。 それでは以下、問題とその解答を見ていきましょう。 問題 ファイルをディレクトリ内に作成する際、同じ名前のファイルがあると、末尾に数字を付けるなどして同じ名前にならないようにします。 こうし...
【夏のミステリー】殺人現場のコード 解答と解説... 【夏のミステリー】殺人現場のコード 本問題は、表題のテーマで、簡単なプログラムを書くものです。 それでは以下、問題とその解答を見ていきましょう。 問題 殺人現場にプログラマが倒れていて、途中までプログラムが書かれている。 「続きを書いて欲しい」 これはダイイングメッセージなのか? どう...
【夏のミステリー】時間制限の密室 解答と解説... 【夏のミステリー】時間制限の密室 本問題は、表題のテーマで、簡単なプログラムを書くものです。 それでは以下、問題とその解答を見ていきましょう。 問題 (なんやかんやあって)命からがら逃げてきた、あなた。 しかし逃げ込んだ部屋にあなたが入った途端、自動でドアはロックされ、しかも10分後にはガ...
数学の問題をプログラミングで解こう!「ウッド・キーパー」問題解説... 問題のおさらい n 本の丸太があります。これらの向きと端をそろえ、地面に積みます。 積む際には次のルールに従います。 地面には好きな本数の丸太を置けます。隣り合う丸太は接して置きます。 左右に隣り合う 2 本の丸太の上に、新たな丸太を 1 本置けます。 全ての丸太は一...

今週のPickUPレポート

新着記事

週間ランキング

CodeIQとは

CodeIQ(コードアイキュー)とは、自分の実力を知りたいITエンジニア向けの、実務スキル評価サービスです。

CodeIQご利用にあたって
関連サイト
codeiq

リクルートグループサイトへ