ガジェット通信 GetNews

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

数学の問題をプログラミングで解こう!「スパイラル・ウォーク」問題解説

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

問題のおさらい

自然数 w, h に対し、横と縦の長さがそれぞれ w, h となる格子状の道を考えます。

この左上の点からスタートして、同じ交差点を二度以上通らないように、らせんを描いて進みます。 br>
最初は下方向にまっすぐ進み、これ以上前に進めなくなったところで左折し、再びまっすぐ進みます。 br>
これを繰り返し、全ての交差点に到達したところで終了します。

(w, h)=(4, 3) の場合の進み方を下に示します。このとき進んだ距離は 19 であることが分かります。

数学の問題をプログラミングで解こう!「スパイラル・ウォーク」問題解説

自然数 m に対し、上のように進んだ時の距離がちょうど m となるような組 (w, h) の個数を F(m) と定義します。

例えば F(11)=4 です。進んだ距離が 11 となる組 (w, h) は、(1, 5), (2, 3), (3, 2), (5, 1) の 4 通りです。

数学の問題をプログラミングで解こう!「スパイラル・ウォーク」問題解説

同様に、F(3)=1, F(23)=6, F(28)=0 となることが確かめられます。

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

例えば、G(11)=12, G(100)=283, G(1000)=5076 となることが確かめられます。

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

方針:進んだ距離の公式を導こう

格子の道をらせん状に歩くときの歩数に関する問題です。一見して難しそうな問題です。順を追ってみていきましょう。

本問を解く一つ目のポイントが、横と縦の長さ w, h を用いて、進んだ距離を表すことです。答えから書くと、次のようになります。

数学の問題をプログラミングで解こう!「スパイラル・ウォーク」問題解説

この公式の導出にはいろいろなやり方があります。ひとつの例を示します。下の図のように、経路の長さを保ちながら変形を行います(w≦h とします)。

数学の問題をプログラミングで解こう!「スパイラル・ウォーク」問題解説

h が偶数の場合と奇数の場合で書き分けていますが、いずれも最終的には、長さ w の横棒が h 本と、長さ h の縦棒が 2 本と、長さ w-h の横棒が 1 本となります。これらの長さを全て足すと、w・h+w+h となります。w≧h の場合については省略しますが、ほぼ同じ議論です。

さて、進んだ距離の公式は得られました。次は F(m) の求め方を考えましょう。m に対し、w・h+w+h = m となる (w, h) の組はいくつあるか、ということですね。次のように式を変形することがポイントです。

数学の問題をプログラミングで解こう!「スパイラル・ウォーク」問題解説

m+1 が 2 つの整数の積で表されました。(w, h) は、そのような表し方の一つ一つに対応します。つまり、F(m) とは、m+1 の約数(ただし 1 と m+1 自身を除く)の個数に他ならないということです。

これでとりあえずの解法のめどがつきました。m+1 の約数をいろんな整数で割ってみて、割り切れる整数の個数がすなわち F(m) です。これを様々な m について計算して和を出せば G(n) が求められそうです。以下は python のコード例です。

n = int(input())
answer = 0
for m in range(1, n+1):
for q in range(2, m+1):
if (m+1) % q == 0: answer += 1
print answer

ただこのコードでは時間がかかり過ぎます。この 2 重ループのコードでは、n に対し n2 回程度の計算を要するため、106 のような大きな n に対しては、1 秒の制限時間内に処理を終えることができません。内側のループの書き方に多少の工夫の余地はありますが、それでも不十分です。

高速化:視点をヨコからタテへ!

高速化を考えましょう。ここで必要なのが、m をいろいろ変えながら足していくという考え方からの脱却です。まずは、いろいろな m+1 の値に対する m+1 の約数を表にしてみましょう。

数学の問題をプログラミングで解こう!「スパイラル・ウォーク」問題解説

さて、上のコードでは、この表を横方向に見て、いろんな数での試し割りをやり、それを1行1行繰り返していたわけです。ここで視点を変えて、縦方向で考えてみましょう。こんな感じです。

数学の問題をプログラミングで解こう!「スパイラル・ウォーク」問題解説

こうするとパターンが見えてくると思います。例えば 3 という約数は、3 から始めて 3 個おきに現れています。第 X 行目までには 3 は計 floor(X / 3) 回現れます(floor:小数点以下を切り捨てる関数)。つまり、縦1列に現れる個数の計算が、割り算一発でできてしまうわけです。これを各列について繰り返せば、先ほどよりはるかに少ない計算量で答えが出せます。

コード例は以下です。これで計算回数は n 回程度となり、1 秒の制限時間でクリア可能になります。m+1 の約数のうち 1 と m+1 自身を除外するため、最後に 2n+1 を引いています。

n = int(input())
answer = 0
for k in range(1, n+2):
answer += (n + 1) / k
answer -= 2 * n + 1
print answer

最後にさらなる高速化を示します。上のコードの for 文は、要するに、x ・y ≦ n+1 となるような自然数の組 (x, y) はいくつあるか? を求めているわけです。ここで x と y の対称性が活用できます。同じ話は以前の記事で紹介しましたのでそちらをご覧ください(数学の問題をプログラミングで解こう!「セカンド・イクエイション」問題解説)。これで計算回数は √n 回程度となり、さらに短い時間で答えが出せます。

import math

n = int(input())
answer, s = 0, int(math.sqrt(n + 1))
for k in range(1, s+1):
answer += 2 * ((n + 1) / k)
answer -= s * s + 2 * n + 1
print answer

みんなのコード

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

CodeIQ「スパイラル・ウォーク」問題 みんなのコード

CodeIQ運営事務局より

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

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