CodeIQ MAGAZINECodeIQ MAGAZINE

数学の問題をプログラミングで解こう!「マルチプル・テーブル」問題解説

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

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

「数学の問題をプログラミングで解こう!」シリーズ。
かけ算表をうまく囲って和を求められた数にするという問題でした。

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

問題のおさらい

下図のようなかけ算表を考えます。

左上のマスを起点に、右と下にマスがどこまでも続いています。
上から i 行目、左から j 列目のマスには、 i×j の値が書き込まれています。

ここに、罫線に沿った四角形で数字を囲います。
自然数 n に対し、囲われた中の数字の和が n に等しくなるような囲い方の数を F(n) と定義します。

例えば、F(9) = 10 です。題意を満たす囲い方は下記の 10 通りです。
なお、ある囲い方が別の囲い方と部分的に重なっていてもかまいません。
(重なりを見やすくするため、下図では複数の色を使って表しています)

同様に、F(15) = 16、F(25) = 10 となることが確かめられます。

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

方針

ある四角形を変数で定義し、その変数を使って、囲われた数字の和を表してみましょう。

ここでは、4 つの変数 x, y, w, h で四角形を定義します。四角形の左上角のマスを左から x 行目、上から y 列目のマスとします(1 ≦ x, y)。四角形の横の長さを w、縦の長さを h とします(1 ≦ w, h)。

次に、x, y, w, h を使って、囲われた数字の和を表してみましょう。これには、和のΣ(シグマ)を用いた計算を行います。正の整数 i, j を用いて、四角形の中の一つのマスを、左端から i 列目、上端から j 行目のマスと表しましょう。このマスは、表全体では左から xi-1 列目、上から yj-1 行目です。よって値として(xi-1)・(yj-1)が書き込まれています。また、i, j の範囲は、それぞれ 1 ≦ iw、1 ≦ jh です。したがって、この範囲での値の和は次のようになります。

これを計算します。

さて、この値が n に等しくなるわけです。イコール n でつなぎ、1/4 を移項すると、次のようになります。

つまり本問は、上式を満たす正の整数 (x, y, w, h) の組が全部でいくつあるかを求める問題だということです。

実装

そのような組はどのように見つければよいでしょうか。ここで上式をじっと見ましょう。左辺が 4 つの項の積になっています。

そこで、4n を 4 つの整数の積として分解するやり方を列挙しましょう。そしてその 4 つの整数がそれぞれ w, h, 2xw-1, 2yh-1 に等しいとしたときの (x, y, w, h) が、題意を満たし得るということです。

4n を 4 つの整数の積に分解するコードには、様々な書き方があります。ここでは一つの書き方として、始めに 4n の約数のリストを作成して、次にこのリストに対する多重ループで 4 つの整数の候補を挙げます。この 4 つの整数を順に w, h, 2xw-1, 2yh-1 としたときの x, y がどちらも正の整数になるかどうかをチェックしましょう。

コード例は以下です。

n = int(input())
m = 4 * n
# mの約数のリストを作る
v = []
d = 1
while True:
    if d * d > m: break
    if m % d == 0:
        v.append(d)
        if d * d != m: v.append(m / d)
    d += 1

answer = 0
# 積が4nとなる4変数w,h,p,qを列挙
for w in v:
    for h in v:
        for p in v:
            if m % (w * h * p) != 0: continue
            q = m / (w * h * p)
            if q == 0: continue
            # xの値が正の整数かどうかチェック
            if (p - h + 1) % 2 != 0: continue
            x = (p - h + 1) / 2
            if x <= 0: continue
            # yの値が正の整数かどうかチェック
            if (q - w + 1) % 2 != 0: continue
            y = (q - w + 1) / 2
            if y <= 0: continue
            answer += 1
print answer

みんなのコード

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

CodeIQ「マルチプル・テーブル」 みんなのコード

CodeIQ運営事務局より

Kawazoeさん、ありがとうございました!
Kawazoeさんの次の問題にご期待ください。

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

■関連記事

【謎解きプログラム】この処理は?【コードを読もう】解答と解説... 【謎解きプログラム】この処理は?【コードを読もう】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 「24時間以...
数学の問題をプログラミングで解こう!「ループ・トラッキング」問題解説... 問題のおさらい 自然数 n に対し、関数 Fn(x) を次のように定義します(floor():床関数)。 例えば n=10, x=1 のとき、F10(1) = floor(4×1×9÷10) = 3 です。 さて、整数 k(0 ≦ k ≦ n)に対して、関数 Fn による変換を繰り返し行い...
【謎解きプログラム】どんな結果になる?【アロー関数】解答と解説... 【謎解きプログラム】どんな結果になる?【アロー関数】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 「24時間...
数学の問題をプログラミングで解こう!「カウント・スリー」問題解説... 問題のおさらい 自然数を 1 から順に書き並べていきます。 このとき、3 の数字が現れる回数を数えます。 自然数 n に対し、ちょうど n 個目の 3 の数字が現れたときに書いている数を F(n) と定義します。 例えば F(10)=35 です。 下の通り、10 個目の 3 は、35 を書いて...
【息抜き】カードを上手く並べよう【言語不問】解答と解説... 【息抜き】カードを上手く並べよう【言語不問】 本問題は、表題のテーマで、簡単なプログラムを書くものです。 それでは以下、問題とその解答を見ていきましょう。 問題 あなたは、11から99までの、89枚のカードを持っています。問題では、横幅と高さの整数が与えられます。この横幅と高さで作られるマス...
【コードミステリ】数字に隠されたメッセージ【言語不問】解答と解説... 【コードミステリ】数字に隠されたメッセージ【言語不問】 本問題は、表題のテーマで、簡単なプログラムを書くものです。 喜屋武ちあきさんによるCodeIQ MAGAZINEでのブックレビューに合わせて、『顔貌売人』(文藝春秋)とのコラボ問題として出題されたものです。 それでは以下、問題とその解...

今週のPickUPレポート

新着記事

週間ランキング

CodeIQとは

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

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

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