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

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

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

問題のおさらい

自然数 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 のコード例です。

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