ガジェット通信

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

数学の問題をプログラミングで解こう!「ディビジョン・ナイン」問題解説

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

問題のおさらい

1 から 4 の数字を使って n 桁の整数を作ります。このとき、9 の倍数となるものを考えましょう。

例えば n = 3 であれば、234、333、441、などが 9 の倍数です。必ずしも 1 から 4 の全ての数字を使う必要はありません。

1 から 4 の数字を使って作る n 桁の整数のうち、9 の倍数となるものの個数を F(n) と定義します。

例えば、F(1) = F(2) = 0、F(3) = 10、F(4) = 40 となることが確かめられます。

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

方針

4 つの数字を並べて 9 の倍数を作る問題です。

本問は、いろいろな解き方ができる問題です。いろいろな解き方でクリアできるよう、n ≦ 20 というあえて少し緩めの上限としました。まずはうまくいかない解法を紹介した後で、解法を 3 つ紹介します。

総当たりではうまくいかない

まずはうまくいかない解法として、1~4 の全ての並べ方を総当たりする解法を紹介します。桁を一つ選んでこれまで選んだ桁に足していく処理を再帰的に繰り返していくというものです。以下は python のコードです。

def next(d, m):
if d == 0:
return 1 if m % 9 == 0 else 0
ret = 0
for i in range(1, 5):
ret += next(d – 1, 10 * m + i)
return ret

n = int(input())
print next(n, 0)

しかし、このコードは時間がかかり過ぎてしまいます。取り得るパターンが全部で最大で 420≒1012 通りもあるため、1 秒という制限時間では全てをチェックできないためです。

解法1:再帰+メモ化で高速化

このコードを高速化しましょう。有効なアプローチが メモ化 です。

再帰関数の呼び出しの結果をそのときの引数と一緒に覚えて(メモして)おき、後で同じ引数で呼ばれたときに再計算せずにメモしておいた結果を返すというテクニックです。メモ化を使えるように、まずは、これまで選んだ桁の値そのものを引数にするのではなく、それを 9 で割った値を引数にしましょう。計算途中で余りの計算をしても、全体の余りの計算結果には影響しません。そして、これまで選んだ桁数 d と、桁の値を 9 で割った値 m の組 (d, m) に対してメモを作成しましょう。以下のコードでは python の辞書型を使っています。

memo = {}

def next(d, m):
if d == 0:
return 1 if m % 9 == 0 else 0
if memo.has_key((d, m)):
return memo[(d, m)]
ret = 0
for i in range(1, 5):
ret += next(d – 1, (10 * m + i) % 9)
memo[(d, m)] = ret
return ret

n = int(input())
print next(n, 0)

解法2:各桁の和に着目しよう

さて、他の解法も紹介します。この解法は、各桁の数字の和が 9 で割り切れれば、その数は 9 の倍数である という特徴を利用します。証明に関しては下記ページなどを参照して下さい。

参考:主な倍数の見分け方(外部サイト)

まず 1~4 の各数字をそれぞれ何個使うかを決めます。その数字の和が 9 で割り切れるなら、それらを並べて作った数は全て 9 の倍数になります。

例を見ましょう。1, 2, 3, 4 をそれぞれ 5 個、3 個、1 個、1 個使ったとしましょう。この数字の和は 1×5+2×3+3×1+4×1 = 18 です。18 は 9 で割り切れますから、これらを並べ替えて作った数はすべて 9 の倍数になります。例えば 1111122234 や 2131214121 はたしかに 9 の倍数です。

そのような並べ替えは何通りあるでしょうか。これは高校数学の順列の数え上げの知識が役立ちます。下記ページを参照して下さい。1, 2, 3, 4 をそれぞれ a 個、b 個、c 個、d 個使った並べ方は、n!÷a!÷b!÷c!÷d! 通りです。

参考:同じものがあるときの順列(外部サイト)

コードを以下に示します。ひと工夫として、階乗の計算を簡単化するために、あらかじめ計算した結果を再利用しています。

n = int(input())
# あらかじめ階乗を計算
f = [1] * (n + 1)
for i in range(1, n + 1):
f[i] = i * f[i-1]

answer = 0
for a in range(0, n + 1):
for b in range(0, n + 1):
for c in range(0, n + 1):
d = n – a – b – c
if d < 0: continue
if (a + 2*b + 3*c + 4*d) % 9 == 0:
answer += f[n] / f[a] / f[b] / f[c] / f[d]
print answer

解法3:行列のべき乗に帰着させる

こんな解き方も可能です。問題を拡張します。1 から 4 の数字を使って作る n 桁の整数のうち、9 で割った余りが r となるものの個数を G(n, r) と定義しましょう。

まずは G(n, 0) の求め方を考えます。以前にも紹介した、一つ手前の状態を考えることが役立ちます(数学の問題をプログラミングで解こう!「プラス・マイナス・ゼロ」問題解説)。すべての n 桁の数を、最後の桁にどの数字が入るかで場合分けします。1 の場合、残りの n-1 桁を 9 で割った余りが 8 であれば、全体は 9 で割り切れます。2 の場合、残りを 9 で割った余りが 7 であれば、全体は 9 で割り切れます。3 の場合は、残りを 9 で割った余りが 6 であれば、全体は 9 で割り切れます。4 の場合は、残りを 9 で割った余りが 5 であれば、全体は 9 で割り切れます。つまり、次の漸化式が成り立つということです。

  G(n, 0) = G(n-1, 8)+G(n-1, 7)+G(n-1, 6)+G(n-1, 5)

G(n, 0) 以外についても、同様に漸化式が導けます。(ここまでは解法1と本質的には同じです。)

  G(n, 1) = G(n-1, 0)+G(n-1, 8)+G(n-1, 7)+G(n-1, 6)
  G(n, 2) = G(n-1, 1)+G(n-1, 0)+G(n-1, 8)+G(n-1, 7)
  G(n, 3) = G(n-1, 2)+G(n-1, 1)+G(n-1, 0)+G(n-1, 8)
  G(n, 4) = G(n-1, 3)+G(n-1, 2)+G(n-1, 1)+G(n-1, 0)
  G(n, 5) = G(n-1, 4)+G(n-1, 3)+G(n-1, 2)+G(n-1, 1)
  G(n, 6) = G(n-1, 5)+G(n-1, 4)+G(n-1, 3)+G(n-1, 2)
  G(n, 7) = G(n-1, 6)+G(n-1, 5)+G(n-1, 4)+G(n-1, 3)
  G(n, 8) = G(n-1, 7)+G(n-1, 6)+G(n-1, 5)+G(n-1, 4)

さらに次のように行列で表しましょう。

ここまでできれば、あとは以前に紹介した行列のべき乗の方法が使えます(数学の問題をプログラミングで解こう!「ルート・パワー」問題解説)。この 9×9 行列を n 乗したときの (1, 1) 成分が、求めるべき G(n, 0) の値です。n が非常に大きくても、計算回数を log n の定数倍まで抑えることが可能です。

コード例は以下です。

def mul(x, y):
z = [[0 for i in range(9)] for j in range(9)]
for i in range(9):
for j in range(9):
for k in range(9):
z[i][j] += x[i][k] * y[k][j]
return z

def pow(x, m):
if m == 1: return x
if m % 2 == 0:
p = pow(x, m / 2)
return mul(p, p)
else:
p = pow(x, m – 1)
return mul(x, p)

matrix = [
[0, 0, 0, 0, 0, 1, 1, 1, 1],
[1, 0, 0, 0, 0, 0, 1, 1, 1],
[1, 1, 0, 0, 0, 0, 0, 1, 1],
[1, 1, 1, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 1, 0, 0, 0, 0, 0],
[0, 1, 1, 1, 1, 0, 0, 0, 0],
[0, 0, 1, 1, 1, 1, 0, 0, 0],
[0, 0, 0, 1, 1, 1, 1, 0, 0],
[0, 0, 0, 0, 1, 1, 1, 1, 0]
]

n = int(input())
p = pow(matrix, n)
print p[0][0]

みんなのコード

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

CodeIQ「ディビジョン・ナイン」問題 みんなのコード

CodeIQ運営事務局より

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

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

TOP