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
  • このエントリーをはてなブックマークに追加

■関連記事

【コードミステリ】数字に隠されたメッセージ【言語不問】解答と解説... 【コードミステリ】数字に隠されたメッセージ【言語不問】 本問題は、表題のテーマで、簡単なプログラムを書くものです。 喜屋武ちあきさんによるCodeIQ MAGAZINEでのブックレビューに合わせて、『顔貌売人』(文藝春秋)とのコラボ問題として出題されたものです。 それでは以下、問題とその解...
数学の問題をプログラミングで解こう!「ディバイド・アウト」問題解説... 問題のおさらい 自然数 n と素数 p に対し、n の階乗(n!)を p でこれ以上割り切れなくなるまで繰り返し割り、その商をさらに p で割ったときの余りを F(n, p) と定義します。 例えば F(12, 5)=4 です。 12!(=479001600)は 5 で最大 2 回割ることができ...
【息抜き】ファイル名を作ろう【言語不問】解答と解説... 【息抜き】ファイル名を作ろう【言語不問】 本問題は、表題のテーマで、簡単なプログラムを書くものです。 それでは以下、問題とその解答を見ていきましょう。 問題 ファイルをディレクトリ内に作成する際、同じ名前のファイルがあると、末尾に数字を付けるなどして同じ名前にならないようにします。 こうし...
【夏のミステリー】殺人現場のコード 解答と解説... 【夏のミステリー】殺人現場のコード 本問題は、表題のテーマで、簡単なプログラムを書くものです。 それでは以下、問題とその解答を見ていきましょう。 問題 殺人現場にプログラマが倒れていて、途中までプログラムが書かれている。 「続きを書いて欲しい」 これはダイイングメッセージなのか? どう...
数学の問題をプログラミングで解こう!「キャンディ・アンド・チョコレート」問題解説... 問題のおさらい n 個のキャンディをグループに分けます。 グループの最大のキャンディの個数が k 個となるような分け方の数を F(n, k) と定義します。 例えば、F(8, 3)=5 です。このときの分け方を以下に示します。 なお個々のキャンディを区別せずに扱う点に注意してください。 同...
【夏のミステリー】時間制限の密室 解答と解説... 【夏のミステリー】時間制限の密室 本問題は、表題のテーマで、簡単なプログラムを書くものです。 それでは以下、問題とその解答を見ていきましょう。 問題 (なんやかんやあって)命からがら逃げてきた、あなた。 しかし逃げ込んだ部屋にあなたが入った途端、自動でドアはロックされ、しかも10分後にはガ...

今週のPickUPレポート

新着記事

週間ランキング

CodeIQとは

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

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

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