CodeIQ MAGAZINECodeIQ MAGAZINE

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

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

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

「数学の問題をプログラミングで解こう!」シリーズ。
整数に変換を繰り返すときの回数に関する問題でした。
素朴にコードを書くと時間がかかりますが、うまく高速化しましょう。

みなさんはうまくできましたか?
ぜひ出題者のKawazoeさんによる本記事で解法をチェックしてください!
by CodeIQ運営事務局

問題のおさらい

自然数 n に対し、関数 Fn(x) を次のように定義します(floor():床関数)。

例えば n=10, x=1 のとき、F10(1) = floor(4×1×9÷10) = 3 です。

さて、整数 k(0 ≦ kn)に対して、関数 Fn による変換を繰り返し行います。

例えば n=10, k=1 のとき、F10 で 1 を変換すると 3 となり、さらに変換すると 8 となります。

以降、1 → 3 → 8 → 6 → 9 → 3 → 8 → … と値が変わっていきます。

このように変換を繰り返したときに、今までに出た値が再度現れるまでの変換回数を G(n, k) と定義します。

例えば G(10, 1)=5 です。5 回目の変換で 3 の値が再度現れていることが分かります(上の太字部分)。

同様に、G(10, 6)=4, G(10, 0)=1, G(10, 5)=3, G(20, 6)=8 となることが確かめられます。

0 以上 n 以下の全ての整数 k に対する G(n, k) の和を H(n) と定義します。

例えば H(10)=42, H(20)=91, H(100)=1118 となることが確かめられます。

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

素朴な方法ではうまくいかない

関数による変換を繰り返し行って、循環する部分を検出する問題です。まずは素朴に G(n, k) を計算する方法を試してみて、その後で高速化の手法を考えてみます。

まずは素朴に解いてみましょう。循環を検出するにはいくつかのやり方が考えられます。ここでは一例として、集合を表すデータ型をつかいます。Python では set という名前で提供されています。整数 k を関数 Fn で次々と変換し、値を set に入れていきます。変換した値が set の中にすでにあるかどうかを都度チェックし、もしあればそれまでの計算回数を G(n, k) としましょう。コードは次のようになります(Python)。

def f(x):
    return (4*x*(n-x))/n

def g(k):
    done = set()
    x, c = k, 0
    while x not in done:
        done.add(x)
        x, c = f(x), c + 1
    return c

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

n = input()
print h()

set を使う方法以外にも、循環を検出するアルゴリズムはあります。メモリの消費量が一定に抑えられるフロイドの循環検出法は、知っておいて損はないでしょう。

参考:フロイドの循環検出法(Wikipedia)

方針:過去の計算結果を再利用

しかしこの方法では、1 秒の制限時間で答えを出すことはできません。Fn(x) で繰り返し変換すると、x の値は [0, n] の範囲をあちこち動き回ります。このため G(n, k) は比較的大きな値になります。よって、n の値が大きいと、トータルの計算量は大きくなってしまいます。

そこで本問では、過去の計算結果をうまく再利用して効率的に計算していきましょう。

一つ目のポイントです。下は、n=100 のときに x=1 に繰り返し変換を行ったときの様子です。

  1 → 3 → 11 → 39 → 95 → 19 → 61 → 95

7 回目の変換で 95 が再度現れました。この様子を図にすると次のようになります。

これで G(100, 1)=7 が確定しました。が、実はこの時点でほかにも値が確定したものがあります。経路の途中にある数字です。これらの G は次の赤字のように確定できます。ループをなしている 3 つの数字(95, 61, 19)に対しては同じ値(3)になる点に注意してください。このように、これらの数字についての計算を一気に省略できます。

二つ目のポイントです。今度は x=2 に繰り返し変換を行ったときの様子を見てみましょう。ちょっと長いですが、次のようになります。

15 回の変換の後に 3 にたどり着いています。3 というのは、先ほどの経路で登場しましたね。G(100, 3)=6 でした。ここまで来れば、計算しなくとも、あと 6 回の変換でループにたどり着くことが分かります。したがって、この時点でここまでの途中の数字を含めて一気に値が確定します。

以上の二つのポイントを使って、効率的に値を確定させることができます。

実装

コード例は以下です。ある k から始めて、足取りを変数 step に記録しながら変換を繰り返します。足取りと同じ値にぶつかったとき(上の一つ目のパターン)は、足取りのすべての値に対する G(n, k) の値を確定させます。確定済みの値は cache という辞書型の変数に覚えておきます。変換の途中で cache にぶつかったとき(上の二つ目のパターン)も、これまでの足取りに対する G(n, k) の値を確定させます。

def f(x):
    return (4*x*(n-x))/n

def g(k, cache):
    x, y, c, step = k, k, 0, dict()
    while True:
        if x in step: # 足取りと同じ値にぶつかる
            for i in range(c):
                cache[y] = max(len(step) - step[x], c - i)
                y = f(y)
            break
        if x in cache: # 確定済みの値にぶつかる
            for i in range(c):
                cache[y] = cache[x] + c - i
                y = f(y)
            break
        step[x], x, c = c, f(x), c + 1
    return cache[k]

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

n = input()
print h()

みんなのコード

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

CodeIQ「ループ・トラッキング」問題 みんなのコード

CodeIQ運営事務局より

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

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

■関連記事

【謎解きプログラム】この処理は?【コードを読もう】解答と解説... 【謎解きプログラム】この処理は?【コードを読もう】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 「24時間以...
【謎解きプログラム】どんな結果になる?【アロー関数】解答と解説... 【謎解きプログラム】どんな結果になる?【アロー関数】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 「24時間...
数学の問題をプログラミングで解こう!「カウント・スリー」問題解説... 問題のおさらい 自然数を 1 から順に書き並べていきます。 このとき、3 の数字が現れる回数を数えます。 自然数 n に対し、ちょうど n 個目の 3 の数字が現れたときに書いている数を F(n) と定義します。 例えば F(10)=35 です。 下の通り、10 個目の 3 は、35 を書いて...
【息抜き】カードを上手く並べよう【言語不問】解答と解説... 【息抜き】カードを上手く並べよう【言語不問】 本問題は、表題のテーマで、簡単なプログラムを書くものです。 それでは以下、問題とその解答を見ていきましょう。 問題 あなたは、11から99までの、89枚のカードを持っています。問題では、横幅と高さの整数が与えられます。この横幅と高さで作られるマス...
【コードミステリ】数字に隠されたメッセージ【言語不問】解答と解説... 【コードミステリ】数字に隠されたメッセージ【言語不問】 本問題は、表題のテーマで、簡単なプログラムを書くものです。 喜屋武ちあきさんによるCodeIQ MAGAZINEでのブックレビューに合わせて、『顔貌売人』(文藝春秋)とのコラボ問題として出題されたものです。 それでは以下、問題とその解...
数学の問題をプログラミングで解こう!「ディバイド・アウト」問題解説... 問題のおさらい 自然数 n と素数 p に対し、n の階乗(n!)を p でこれ以上割り切れなくなるまで繰り返し割り、その商をさらに p で割ったときの余りを F(n, p) と定義します。 例えば F(12, 5)=4 です。 12!(=479001600)は 5 で最大 2 回割ることができ...

今週のPickUPレポート

新着記事

週間ランキング

CodeIQとは

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

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

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