CodeIQ MAGAZINECodeIQ MAGAZINE

数学の問題をプログラミングで解こう!「ウッド・キーパー」問題解説

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

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

「数学の問題をプログラミングで解こう!」シリーズ。
丸太の積み方に関する問題でした。
かなりの難問だったようです。
が、ある視点に気が付くと、比較的シンプルなコードで解くことができます。

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

問題のおさらい

n 本の丸太があります。これらの向きと端をそろえ、地面に積みます。

積む際には次のルールに従います。

  • 地面には好きな本数の丸太を置けます。隣り合う丸太は接して置きます。
  • 左右に隣り合う 2 本の丸太の上に、新たな丸太を 1 本置けます。
  • 全ての丸太は一つながりになっていないといけません。

n=11 のときの置き方をいくつか示します。
横から見た図です。上の 2 つは正しい置き方ですが、下の 3 つは正しくない置き方です。

n 本の丸太の可能な置き方の総数を F(n) と定義します。

例えば F(5)=5 です。可能な置き方を以下に示します。

同様に、F(1)=1, F(3)=2, F(4)=3, F(11)=135 となることが確かめられます。

標準入力から、自然数 n (1 ≦ n ≦ 60)が与えられます。
標準出力に F(n) の値を出力するプログラムを書いてください。

方針:視線を斜めに!

丸太をルールにしたがって並べる問題です。n の値が 6 や 7 ぐらいまでなら、ノートに全てのパターンを描き切れますが、それより大きな n になると途端にパターン数が多くなり、手で描き切ることは不可能になります。

さて、本問では、これまでにたびたび登場した「一つ手前の状態を考える」というアプローチが有効です(数学の問題をプログラミングで解こう!「プラス・マイナス・ゼロ」問題解説)。ただ、本問では一筋縄ではうまくいきません。率直には、図を横方向に見て、一つ下の段に k 個の丸太があるとして、その上の積み方を考えたくなるわけですが・・・、実際考えてみると分かりますが、最終的に漸化式の形に落とし込むことはむずかしいです。

そこで発想の転換が必要です。図を横方向に見るのでなく、斜め方向に見ましょう。下図のように、各点線上の丸太の本数を書き並べてみます。すると、自然数の列ができ上がります。

題意を満たす丸太の積み方と、この数列には、どのような関係があるでしょうか。それはいたってシンプルです。左端の数字はかならず 1 であること。そして、ある数字は、その左隣りの数字より 2 以上大きくなってはいけません。

要するに、F(n) とは、「和が n となる自然数を、左端が 1 で、かつ、どの数字もその左隣りより 2 以上大きくならないように並べる場合の数」に他ならないということです。

これを求めるために次の関数を定義しましょう。ある数字 d の右側に、和が m となる自然数を並べる場合の数を G(m, d) と定義します。

G(m, d) はシンプルな漸化式で表すことができます。左端の数字に注目して場合分けしましょう。これの一つ左の数字は d です。左端の数字はこれより 2 以上大きくなってはいけません。したがって、左端に来ることができる数字は、1 から d+1 の間の数字です。

また、左端の数字が k であるとき、残りの並べ方は G(mk, k) 通りとなります。以上から、G(m, d) の漸化式は次のようになります。

そして求めるべき F(n) とは、G(n, 0) のことです。G(m, d) を求める実装を考えましょう。

実装

ここまでくれば、実装は比較的シンプルです。再帰をつかって漸化式を繰り返し呼ぶコードを書きましょう。ただ単純な再帰だと、計算量がネズミ算式に増えてしまいます。いちど計算した引数の組 (m, d) については、結果をキャッシュとして覚えておいて、同じ組の結果が必要になったときには、再計算せずにキャッシュの値を再利用します。(「メモ化再帰」というテクニックです。)

このように、「一つ手前の状態を考える」→「漸化式を立てる」→「メモ化再帰のコードを書く」というのは一連のパターンです。ぜひ慣れておきましょう。

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

def g(m, d):
    if m == 0: return 1
    if m < 0: return 0
    if dic.has_key((m, d)): return dic[(m, d)]
    a = 0
    for k in range(1, d+2):
        a += g(m-k, k)
    dic[(m, d)] = a
    return a

dic = dict()
n = input()
print g(n, 0)

みんなのコード

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

CodeIQ「ウッド・キーパー」問題 みんなのコード

CodeIQ運営事務局より

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

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

■関連記事

【夏のミステリー】殺人現場のコード 解答と解説... 【夏のミステリー】殺人現場のコード 本問題は、表題のテーマで、簡単なプログラムを書くものです。 それでは以下、問題とその解答を見ていきましょう。 問題 殺人現場にプログラマが倒れていて、途中までプログラムが書かれている。 「続きを書いて欲しい」 これはダイイングメッセージなのか? どう...
数学の問題をプログラミングで解こう!「キャンディ・アンド・チョコレート」問題解説... 問題のおさらい n 個のキャンディをグループに分けます。 グループの最大のキャンディの個数が k 個となるような分け方の数を F(n, k) と定義します。 例えば、F(8, 3)=5 です。このときの分け方を以下に示します。 なお個々のキャンディを区別せずに扱う点に注意してください。 同...
【夏のミステリー】時間制限の密室 解答と解説... 【夏のミステリー】時間制限の密室 本問題は、表題のテーマで、簡単なプログラムを書くものです。 それでは以下、問題とその解答を見ていきましょう。 問題 (なんやかんやあって)命からがら逃げてきた、あなた。 しかし逃げ込んだ部屋にあなたが入った途端、自動でドアはロックされ、しかも10分後にはガ...
【息抜き】平均値と中央値【言語不問】解答と解説... 【息抜き】平均値と中央値【言語不問】 本問題は、表題のテーマで、簡単なプログラムを書くものです。 それでは以下、問題とその解答を見ていきましょう。 問題 改行区切りの文字列の各行(最大行数30)は、半角数字のみの整数(最大桁数8)になっています。 この各行の平均値と中央値を求めて下さい。小...
【息抜き】右位置揃え【言語不問】解答と解説... 【息抜き】右位置揃え【言語不問】 本問題は、表題のテーマで、簡単なプログラムを書くものです。 それでは以下、問題とその解答を見ていきましょう。 問題 改行区切りの文字列の各行は、半角数字のみの整数(最大桁数32)になっています。 この各行の先頭に任意の数の半角のアンダーバー(_)を挿入して...
【謎解きプログラム】どんな配列が得られる?【フィルター,マップ】解答と解説... 【謎解きプログラム】どんな配列が得られる?【フィルター,マップ】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 ...

今週のPickUPレポート

新着記事

週間ランキング

CodeIQとは

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

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

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