CodeIQ MAGAZINECodeIQ MAGAZINE

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

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

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

「数学の問題をプログラミングで解こう!」シリーズ。格子路をらせん状に歩くときの距離が等しくなる組み合わせを求めるという問題でした。たいへん複雑に見える問題ですが、うまく考えると自然数の約数の個数を求めるという問題に帰着でき、シンプルなコードで答えを出せます。

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

問題のおさらい

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

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

(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≦mn となる全ての m に対する F(m) の和を G(n) と定義します。

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

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

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

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

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

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

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

さて、進んだ距離の公式は得られました。次は F(m) の求め方を考えましょう。m に対し、whwhm となる (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 文は、要するに、xyn+1 となるような自然数の組 (x, y) はいくつあるか? を求めているわけです。ここで xy の対称性が活用できます。同じ話は以前の記事で紹介しましたのでそちらをご覧ください(数学の問題をプログラミングで解こう!「セカンド・イクエイション」問題解説)。これで計算回数は √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さんの最新問題が出題中です。
ぜひ挑戦してみてくださいね!

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

■関連記事

【夏のミステリー】殺人現場のコード 解答と解説... 【夏のミステリー】殺人現場のコード 本問題は、表題のテーマで、簡単なプログラムを書くものです。 それでは以下、問題とその解答を見ていきましょう。 問題 殺人現場にプログラマが倒れていて、途中までプログラムが書かれている。 「続きを書いて欲しい」 これはダイイングメッセージなのか? どう...
数学の問題をプログラミングで解こう!「キャンディ・アンド・チョコレート」問題解説... 問題のおさらい n 個のキャンディをグループに分けます。 グループの最大のキャンディの個数が k 個となるような分け方の数を F(n, k) と定義します。 例えば、F(8, 3)=5 です。このときの分け方を以下に示します。 なお個々のキャンディを区別せずに扱う点に注意してください。 同...
【夏のミステリー】時間制限の密室 解答と解説... 【夏のミステリー】時間制限の密室 本問題は、表題のテーマで、簡単なプログラムを書くものです。 それでは以下、問題とその解答を見ていきましょう。 問題 (なんやかんやあって)命からがら逃げてきた、あなた。 しかし逃げ込んだ部屋にあなたが入った途端、自動でドアはロックされ、しかも10分後にはガ...
数学の問題をプログラミングで解こう!「ウッド・キーパー」問題解説... 問題のおさらい n 本の丸太があります。これらの向きと端をそろえ、地面に積みます。 積む際には次のルールに従います。 地面には好きな本数の丸太を置けます。隣り合う丸太は接して置きます。 左右に隣り合う 2 本の丸太の上に、新たな丸太を 1 本置けます。 全ての丸太は一...
【息抜き】平均値と中央値【言語不問】解答と解説... 【息抜き】平均値と中央値【言語不問】 本問題は、表題のテーマで、簡単なプログラムを書くものです。 それでは以下、問題とその解答を見ていきましょう。 問題 改行区切りの文字列の各行(最大行数30)は、半角数字のみの整数(最大桁数8)になっています。 この各行の平均値と中央値を求めて下さい。小...
【息抜き】右位置揃え【言語不問】解答と解説... 【息抜き】右位置揃え【言語不問】 本問題は、表題のテーマで、簡単なプログラムを書くものです。 それでは以下、問題とその解答を見ていきましょう。 問題 改行区切りの文字列の各行は、半角数字のみの整数(最大桁数32)になっています。 この各行の先頭に任意の数の半角のアンダーバー(_)を挿入して...

今週のPickUPレポート

新着記事

週間ランキング

CodeIQとは

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

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

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