CodeIQ MAGAZINECodeIQ MAGAZINE

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

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

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

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

みなさんはうまくできましたか?
ぜひ出題者の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
  • このエントリーをはてなブックマークに追加

■関連記事

数学の問題をプログラミングで解こう!「ウッド・キーパー」問題解説... 問題のおさらい n 本の丸太があります。これらの向きと端をそろえ、地面に積みます。 積む際には次のルールに従います。 地面には好きな本数の丸太を置けます。隣り合う丸太は接して置きます。 左右に隣り合う 2 本の丸太の上に、新たな丸太を 1 本置けます。 全ての丸太は一...
【息抜き】平均値と中央値【言語不問】解答と解説... 【息抜き】平均値と中央値【言語不問】 本問題は、表題のテーマで、簡単なプログラムを書くものです。 それでは以下、問題とその解答を見ていきましょう。 問題 改行区切りの文字列の各行(最大行数30)は、半角数字のみの整数(最大桁数8)になっています。 この各行の平均値と中央値を求めて下さい。小...
【息抜き】右位置揃え【言語不問】解答と解説... 【息抜き】右位置揃え【言語不問】 本問題は、表題のテーマで、簡単なプログラムを書くものです。 それでは以下、問題とその解答を見ていきましょう。 問題 改行区切りの文字列の各行は、半角数字のみの整数(最大桁数32)になっています。 この各行の先頭に任意の数の半角のアンダーバー(_)を挿入して...
【謎解きプログラム】どんな配列が得られる?【フィルター,マップ】解答と解説... 【謎解きプログラム】どんな配列が得られる?【フィルター,マップ】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 ...
数学の問題をプログラミングで解こう!「タンジェント・フラクション」問題解説... 問題のおさらい α と β を、0 < α < β < π/2 を満たす実数とします。 α, β の組のうち、tan(α), tan(β), tan(α+β) がすべて単位分数(分母が自然数、分子が 1 の分数として書き表せる数)となるものを考えましょう。(α, β の単位はラジアンと見なします...
【謎解きプログラム】どう比較する?【ソート】解答と解説... 【謎解きプログラム】どう比較する?【ソート】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 「24時間以内に謎...

今週のPickUPレポート

新着記事

週間ランキング

CodeIQとは

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

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

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