CodeIQ MAGAZINECodeIQ MAGAZINE

数学の問題をプログラミングで解こう!「タワー・ビルディング」問題解説

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

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

「数学の問題をプログラミングで解こう!」シリーズ。
2種類のブロックで塔を作る場合の数に関する問題でした。
いろいろな解き方が可能です。

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

問題のおさらい

A を一辺が 1 の立方体のブロックとし、B を縦が 1、横が 1、高さが 2 の直方体のブロックとします。
(下は横から見た図です。)

自然数 n, a, b に対し、A を最大 a 個、B を最大 b 個使って、縦が 1、横が 1、高さが n の直方体の塔を作ります。
このときの積み上げ方の場合の数を F(n, a, b) と定義します。

例えば F(6, 4, 2)=11 です。以下に示します。

同様に、F(4, 3, 1)=3, F(4, 4, 4)=5, F(5, 2, 1)=0, F(10, 5, 3)=35 です。
また、F(100, 50, 50) を 1000003 で割った余りは 765461 となることが確かめられます。

標準入力から、自然数 n, a, b(1 ≦ n ≦ 500, 0 ≦ an, 0 ≦ bn)が半角空白区切りで与えられます。
標準出力に F(n, a, b) を 1000003 で割った余りを出力するプログラムを書いてください。

方針1:メモ化再帰

いくつかの方針で解くことができます。まず始めに動的計画法の解き方を紹介した後で、二項係数の和を計算する解き方を紹介します。

始めは動的計画法での解き方です。この方法は本シリーズでもたびたび登場しています。塔のいちばん上のブロックの種類に着目することがこの解き方のポイントです。塔の作り方の数 F(n, a, b) を、いちばん上のブロックが A か B かによって場合分けしましょう。

A の場合、残りの部分の作り方はいくつあるでしょうか。残る長さは n-1 です。そしてこの部分を、ブロック A を最大 a-1 個(すでに 1 個使ったのでマイナス 1)、ブロック B を最大 b 個使って作ります。したがってそのような作り方は、F(n-1, a-1, b) 通りです。

B の場合はどうでしょうか。塔の残りの部分の長さは n-2 です。この部分を、ブロック A を最大 a 個、ブロック B を最大 b-1 個使って作りますから、そのような作り方は、F(n-2, a, b-1) 通りです。

以上から、次の関係が成り立つことが分かります。

  F(n, a, b) = F(n-1, a-1, b) + F(n-2, a, b-1)

ここまで来れば、あとはコーディングです。再帰のコードを書きましょう。いちど計算を行った (n, a, b) の組については計算結果を覚えておいて再利用することで計算量を減らしましょう。メモ化再帰というテクニックです。コード例(Python)は次のようになります。

p = 1000003
dic = dict()

def f(n, a, b):
    if a < 0 or b < 0 or n < 0: return 0
    if n == 0: return 1
    if dic.has_key((n,a,b)): return dic[(n,a,b)]
    dic[(n,a,b)] = (f(n-1, a-1, b) + f(n-2, a, b-1)) % p
    return dic[(n,a,b)]

n, a, b = map(int, raw_input().split())
print f(n, a, b)

メモ化再帰の問題は過去にも何度か出題されています。ぜひ参照して下さい。

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

方針2:二項係数の和で求めよう

別の解き方を紹介します。この解き方では、まず始めにブロック B を何個使うかを一つ固定します。そしてそのときの塔のつくり方の場合の数を求め、取り得る場合について和をとるというやり方です。

いま、ブロック B を k 個使うとしましょう。この高さは 2k ですから、残りのブロック A の個数は n-2k 個です。このときの塔の作り方は何通りでしょうか。ブロック A と B の合計 nk 個から、A の k 個を選ぶやり方のことですから、二項係数(コンビネーション)を使って、nkCk となります。

求めるべき答えは、取りえる全ての k に対する nkCk の和です。nkCk の計算には少々の処理量を要しますが、本問では n の上限はたかだか 500 ですので、ひとつひとつの k について nkCk の値をつど計算するやり方でも問題ないでしょう。ここではプラスアルファの高速化の工夫をします。まず nkCk を (nk)!÷k!÷(n-2k)! と表します。見ての通り、階乗(を 1000003 で割った剰余)の計算がたびたび現れます。そこで、階乗の剰余の値をあらかじめ計算しておいて使いまわします。

ここで、上の ÷k! や ÷(n-2k)! のように、割り算を行うには工夫が必要です。1000003 での剰余をもとにした割り算を行うには、1000003 を法とした逆元というものを計算しないといけません。具体的な計算の仕方については下記サイトを参照して下さい。

参考:整数の合同と1次合同式(外部サイト)

コード例(Python)は以下です。fact と inv という配列を用意し、fact[i] と inv[i] には、1000003 を法とした i! とその逆元の値がそれぞれ収められます。inv を効率的に計算するための工夫として、n! の逆元(inv[n])だけを先に求めて、そこに nn-1,n-2,… を掛けてそれぞれ inv[n-1],inv[n-2],inv[n-3],… の値としています。

p = 1000003

def ext_gcd(a, b):
    if a == 0: return b, 0, 1
    g, y, x = ext_gcd(b % a, a)
    return g, x - (b / a) * y, y

# pを法とするnの逆元
def inv_mod(n, p):
    g, x, y = ext_gcd(n, p)
    return ( x + p ) % p if g == 1 else 0

def f(n, a, b):
    fact, inv = [1]*(n+1), [1]*(n+1)
    for i in range(n):
        fact[i+1] = (fact[i] * (i+1)) % p
    inv[n] = inv_mod(fact[n], p)
    for i in range(n):
        inv[n-i-1] = (inv[n-i] * (n-i)) % p
    k_min, k_max = max(0, (n-a+1)/2), min(b, n/2)
    answer = 0
    for k in range(k_min, k_max+1):
        answer = (answer + fact[n-k] * inv[k] * inv[n-2*k]) % p
    return answer % p

n, a, b = map(int, raw_input().split())
print f(n, a, b)

みんなのコード

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

CodeIQ「タワー・ビルディング」問題 みんなのコード

CodeIQ運営事務局より

Kawazoeさん、ありがとうございました!
Kawazoeさんの次回の問題にご期待下さい。

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

■関連記事

数学の問題をプログラミングで解こう!「LCM・パレード」問題解説... 問題のおさらい 自然数 a, b に対し、a と b の最小公倍数を LCM(a, b) と定義します。 例えば、LCM(6, 8)=24 です。 さらに、自然数 n, k に対し、n 以下の全ての自然数 m に対する LCM(k, m)÷k の値の和を F(n, k)と定義します。 例えば ...
【謎解きプログラム】正しいコードは?【仮想くじ引き】解答と解説... 【謎解きプログラム】正しいコードは?【仮想くじ引き】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 「24時間...
【謎解きプログラム】どう防ぐ?【無限ループ】解答と解説... 【謎解きプログラム】どう防ぐ?【無限ループ】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 「24時間以内に謎...
【謎解きプログラム】正しいコードは?【一人すごろく】解答と解説... 【謎解きプログラム】正しいコードは?【一人すごろく】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 「24時間...
数学の問題をプログラミングで解こう!「ペア・ドロップ」問題解説... 問題のおさらい n を自然数とします。1 から n までの自然数が 1 つずつ書かれた n 枚のカードが 2 組あります。 これら 2n 枚のカードをよく混ぜ、A と B の 2 人に n 枚ずつ配ります。 A と B は、それぞれ自分の持ち札の中に番号が一致するカードがあればその 2 枚を捨...
【謎解きプログラム】中身はどうなる?【出し入れ】解答と解説... 【謎解きプログラム】中身はどうなる?【出し入れ】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 「24時間以内...

今週のPickUPレポート

新着記事

週間ランキング

CodeIQとは

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

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

リクルートへ