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

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

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

問題のおさらい

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

例えば、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 以下の整数はいくつあるか?」という問題です。

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

オスカー2018年晴れ着撮影会