読者です 読者をやめる 読者になる 読者になる

IT NoViCe

IT 初心者の勉強備忘録ブログ

スパイラル・ウォーク

問題

という問題を解きました。

今回はCodeIQというサイトで公開されていた問題になります。

codeiq.jp

■問題

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

この左上の点からスタートして、

同じ交差点を二度以上通らないように、らせんを描いて進みます。

最初は下方向にまっすぐ進み、これ以上前に進めなくなったところで左折し、

再びまっすぐ進みます。

これを繰り返し、全ての交差点に到達したところで終了します。

(w, h)=(4, 3) の場合の進み方を下に示します

このとき進んだ距離は 19 であることが分かります。

自然数 m に対し、上のように進んだ時の距離が

ちょうど m となるような組 (w, h) の個数を F(m) と定義します。

 

さらに、自然数 n に対し、

1≦mn となる全ての m に対する F(m) の和を G(n) と定義します。

 

自然数 n が与えられたときG(n) を出力するプログラムを書いてください。

 

という問題です。

だいぶ数学感のある問題ですね。

では、私の考えた道筋と公式の解答を説明していきます。

 

まず (w, h) の時に進む距離 d(w, h) を求めていきます。

私は実際に複数パターンの格子を作図してみて、以下の漸化式を得ました。

① d(w, h) = d(w, h -1) + w +1

② d(w, h) = d(w -1, h) + h +1

上記の① ②式からd(w, h)を計算すると

③ d(w, h) = wh + w + h

と、なります。

 

続いて F(m) を求めます。

1からnまでのF(m) を足し合わせればG(n) となるので、

これさえ求まれば終了になります。

 

まず d(w, h) = m となる条件を探していきます。

上記③式を代入すると、 wh + w + h = m となり、

さらに計算すると (w + 1)(h + 1) = m + 1 となります。

この式を満たす(w, h)の組み合わせが

"距離がちょうど m となるような組(w, h)" と対応します。

また、この式は「(m + 1) を (w + 1) × (h + 1) に分解している」と読めるため、

F(m) は 「(m + 1) の約数の数(1 と 自分自身 は除く) を表している」

ということができます。

 

まとめると、G(n) は 1≦m≦n を満たすmの約数の数の総和 となります。

問題からは考えられないシンプルさになりました。

 

淡々と書いてますが実際はものすごく考えてやっと導出できました。

特に、

・進む距離を漸化式で表し、wh + w +h を導出

・F(m) が約数の数を表していること を発想

のあたりはかなり悩んでようやくできました。

 

そして、上記の考えを反映したコードがこちらです。

 

■ 私の解答

def G(n):
    Sum = 0
    for m in range(1, n+1):
        for k in range(2, m+1):
            if (m+1) % k == 0:
                Sum += 1
    return Sum

 

シンプル!!

 

自分で書いていうのもあれですが

複雑そうな問題がすごい簡単な問題に帰着されました。

(出題者さんのおかげですね・・・)

 

続いて出題者さんの模範解答です。

 

■ 模範解答

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

 

約数を数える際に

m の約数はいくつあるか、m-1 の約数はいくつあるか

という視点ではなく

2が約数になる数がいくつあるか、3が約数になる数はいくつあるか

という視点で考えることで計算回数を減らしています。

また 変数の対象性を利用してさらに計算回数を抑えています。

 

ここまでの発想は私にはできませんでした。

柔軟性のある考えをできるようにならねば・・・

 

実際の問題と解答・説明は下記のページで確認できます。

codeiq.jp

もっといろんな問題をといて数学にもプログラムにも慣れていきたいです。