ガジェット通信 GetNews

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

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

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

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

問題のおさらい

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 ≦ a ≦ n, 0 ≦ b ≦ n)が半角空白区切りで与えられます。
標準出力に 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 の合計 n-k 個から、A の k 個を選ぶやり方のことですから、二項係数(コンビネーション)を使って、n-kCk となります。

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

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

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

コード例(Python)は以下です。fact と inv という配列を用意し、fact[i] と inv[i] には、1000003 を法とした i! とその逆元の値がそれぞれ収められます。inv を効率的に計算するための工夫として、n! の逆元(inv[n])だけを先に求めて、そこに n,n-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さんの次回の問題にご期待下さい。

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