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

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

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

問題のおさらい

自然数 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)になる点に注意してください。このように、これらの数字についての計算を一気に省略できます。

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

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