ガジェット通信 GetNews

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

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

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

問題のおさらい

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

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

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

さて、整数 k(0 ≦ k ≦ n)に対して、関数 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さんの最新問題が出題中です。
ぜひ挑戦してみてくださいね!

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