CodeIQ MAGAZINECodeIQ MAGAZINE

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

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

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

「数学の問題をプログラミングで解こう!」シリーズ。
1~4 の数字を並べて 9 の倍数を作る問題です。今回はいろいろな解き方のできる問題です。本記事ではそのうちのいくつかを紹介します。
みなさんはどんな解き方をしましたか?
ぜひ出題者のKawazoeさんによる本記事で解法をチェックして下さい!
by CodeIQ運営事務局

問題のおさらい

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さんの最新問題が出題中です。
ぜひ挑戦してみてくださいね!

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

■関連記事

【息抜き】平均値と中央値【言語不問】解答と解説... 【息抜き】平均値と中央値【言語不問】 本問題は、表題のテーマで、簡単なプログラムを書くものです。 それでは以下、問題とその解答を見ていきましょう。 問題 改行区切りの文字列の各行(最大行数30)は、半角数字のみの整数(最大桁数8)になっています。 この各行の平均値と中央値を求めて下さい。小...
【息抜き】右位置揃え【言語不問】解答と解説... 【息抜き】右位置揃え【言語不問】 本問題は、表題のテーマで、簡単なプログラムを書くものです。 それでは以下、問題とその解答を見ていきましょう。 問題 改行区切りの文字列の各行は、半角数字のみの整数(最大桁数32)になっています。 この各行の先頭に任意の数の半角のアンダーバー(_)を挿入して...
【謎解きプログラム】どんな配列が得られる?【フィルター,マップ】解答と解説... 【謎解きプログラム】どんな配列が得られる?【フィルター,マップ】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 ...
数学の問題をプログラミングで解こう!「タンジェント・フラクション」問題解説... 問題のおさらい α と β を、0 < α < β < π/2 を満たす実数とします。 α, β の組のうち、tan(α), tan(β), tan(α+β) がすべて単位分数(分母が自然数、分子が 1 の分数として書き表せる数)となるものを考えましょう。(α, β の単位はラジアンと見なします...
【謎解きプログラム】どう比較する?【ソート】解答と解説... 【謎解きプログラム】どう比較する?【ソート】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 「24時間以内に謎...
数学の問題をプログラミングで解こう!「ロンリー・ルーク」問題解説... 問題のおさらい 自然数 n, k に対し、縦横 n×n のマス目にチェスのルークの駒を k 個配置することを考えます。 このとき、自身から見て上下方向・左右方向のいずれにも他の駒が存在しないような駒を「はぐれルーク」と呼びます。 例えば以下は、(n, k)=(4, 5) のときの駒の配置例を示...

今週のPickUPレポート

新着記事

週間ランキング

CodeIQとは

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

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

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