ガジェット通信

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

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

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

問題のおさらい

ある自然数に対し、各桁の数字をすべて足し合わせるという変換を行います。

例えば、199 にこの変換を行うと、1+9+9=19 という数になります。

さらに、得られた数に同様の変換を行います。最終的に 1 桁の数になるまで変換を繰り返し行います。

199 だと、1 回目の変換で 19 になり、2 回目の変換で 10 になり、3 回目の変換で 1 になります。

自然数 k に対し、上の変換を繰り返したときに最終的に 1 桁の数になるまでに必要な変換の回数を F(k) と定義します。

例えば F(199) = 3 です。同様に、F(9) = 0, F(26) = 1, F(888888) = 3 です。

自然数 n に対し、1 ≦ k ≦ n となる全ての k に対する F(k) の和を G(n) と定義します。

例えば G(9) = 0,G(20) = 12,G(149) = 200, G(9876) = 19951 となることが確かめられます。

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

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

桁の数字の和を繰り返しとり 1 桁の数字に変換する処理に関する問題です。一般に、こうして得られた 1 桁の数字は「数字根」と呼ばれています。

まずは単純に解いてみましょう。数字根が得られるまでの計算回数を求める関数 F(k) を実装します。以下のコード例では、k を文字列で表し、各文字を数値としてつぎつぎと足しています。

def f(k):
c = 0
while k >= 10:
r = 0
for d in str(k): r += int(d)
k, c = r, c+1
return c

def g(n):
answer = 0
for k in range(1, n+1):
answer += f(k)
return answer

n = input()
print g(n)

ひとまずこれで答えを出すことは可能です。しかし、今回のように n の上限が 108 という条件では、時間がかかり過ぎて、1 秒以内でクリアすることはできません。

一手後の結果でグループ分けしよう

本問では、F(k) の k をひとつひとつ選んで計算するのではなく、グループに分けてまとめて計算 することで、計算量を抑えましょう。

ここで着目するのは「一手後の値」です。一手後の値とは、各桁の和を一回とった後の値のことです。一手後の値が同じになるような k をまとめて1グループとしましょう。k が大きな値でも、一手でかなり小さくなるため、グループ数はそんなに多くなりません。したがって、グループごとの計算を効率よく行えれば、トータルの計算量を下げられると期待できます。

つまりこういうことです。整数 d をひとつ固定し、「一手後の値が d となる k の個数」を求めます。次に、その d に対する F(d) の値を求めます(これは上の愚直な方法でやってかまいません)。すると、このグループの F(k) の和は、「上記の個数」×「F(d)+1」となります。これを、様々な d について求めて和をとれば、求めるべき G(n) が得られます。

各桁の和が d になる整数の個数は? メモ化再帰で求めよう

以上の考察により、本問は新しい問題へと変わりました。「各桁の和がちょうど d になるような n 以下の整数はいくつあるか?」という問題です。

なにげに骨の折れる問題です。ここでは、まず条件を満たす整数を再帰で全列挙するコードを書き、次にそこにメモ化を導入して高速化する、というアプローチでいきます。

再帰で全列挙するコードを考えるには、下図のような樹形図を書くとよいでしょう。

図は n=234 を例にしています。左端の百の位から始めて、次の桁の数字を選んでいきます。右端の一の位に着いたところで、それまでの数字の和が d に等しいかどうかを調べ、そのようなものの個数を数えればOKです。

次の桁の数字の選び方には注意が必要です。基本的には、0 から 9 の範囲の数字を選べばよいのですが、n に等しい数字をたどっているとき(図のマルで囲った数字です)は、0 から 9 でなく、0 からその桁の数字までの範囲で選ぶようにしましょう。

再帰の全探索のコードは次のようになります。再帰関数 next には 3 つの引数 i, d, b があります。この関数は、樹形図の左端から i 段目のノードを対象に、そこから右にたどったときの和が d となるたどり方の個数を表します。さらにそのノードが図のマルつきかどうかをフラグ b で表しています。

def next(i, d, b):
if i == len(s):
return 1 if d == 0 else 0
r = 0
m = int(s[i]) + 1 if b else 10
for t in range(m):
b_new = b and t == int(s[i])
r += next(i+1, d-t, b_new)
return r

n, d = 12345, 10
s = str(n)
# 桁の和が d となる n 以下の整数の個数
print next(0, d, True)

あとひとふんばりです。このコードは全列挙なので高速ではありません。一度計算した結果をメモしておいて、おなじ引数で二度以上計算をしないようにしましょう。(i, d, b) の組をキーとする辞書型を用意し、計算結果をキャッシュします。これで一気に高速化できます。

最終的なコード例は以下です。注意点として、このコードだと 0 から 9 までの値に対して誤ってカウントしているので、答えから 10 を引き算しています。

def f(k):
c = 0
while k >= 10:
r = 0
for d in str(k): r += int(d)
k, c = r, c+1
return c

dic = dict()
s = ”

def next(i, d, b):
if dic.has_key((i,d,b)): return dic[(i,d,b)]
if i == len(s):
return 1 if d == 0 else 0
r = 0
m = int(s[i]) + 1 if b else 10
for t in range(m):
b_new = b and t == int(s[i])
r += next(i+1, d-t, b_new)
dic[(i,d,b)] = r
return r

def g(n):
if n < 10: return 0
global s
s = str(n)
answer = 0
for d in range(100):
answer += (f(d) + 1) * next(0, d, True)
return answer – 10

n = input()
print g(n)

みんなのコード

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

CodeIQ「デジタル・ルート」 みんなのコード

CodeIQ運営事務局より

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

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

TOP