CodeIQ MAGAZINECodeIQ MAGAZINE

数学の問題をプログラミングで解こう!「キャリー・オーバー」問題解説

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

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

「数学の問題をプログラミングで解こう!」シリーズ。
足し算の繰り上がりの個数に関する問題でした。問題文自体はシンプルですが、解くのは一筋縄ではいきません。

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

問題のおさらい

9606+91377 という足し算を筆算で行いましょう。下のようになります。

この計算では繰り上がりがあります。
例えば、一の位を足すと 6+7=13 です。このとき、十の位に 1 を繰り上げます。
十の位は、繰り上げた 1 を足して、1+0+7=8 と計算します。
同様に、千から一万の位、一万から十万の位でも繰り上がりがあります。
この計算では、計 3 回の繰り上がりがあります。

同様に、71+19 の計算では 1 回、99999+1 の計算では 5 回の繰り上がりがあります。

自然数 nc に対し、0 以上 10n 未満の整数から 2 つ選び、
この 2 つを足し算したときの繰り上がりの回数がちょうど c 回となるものの個数を F(n, c) と定義します。

例えば F(1, 1)=45 です。0 以上 10 未満の 2 つの整数の足し算で、繰り上がりがちょうど 1 回となるものは以下の 45 個です。

同様に、F(1, 0)=55, F(2, 0)=3025, F(2, 1)=4500, F(2, 2)=2475, F(3, 1)=358875 となることが確かめられます。

標準入力から、自然数 nc (1 ≦ n ≦ 8 かつ 0 ≦ cn)が空白区切りで与えられます。
標準出力に F(n, c) を出力するプログラムを書いてください。

一つ前の状態に注目して漸化式を導こう

足し算の繰り上がりに関する問題です。素朴に思いつく方法としては、n 桁以下の 2 整数を列挙して、実際に足し算を行ってみるやり方があります。しかし本問では n の上限は 8 です。最大で 108×108=1016 通りの足し算をチェックする必要があり、時間がかかり過ぎてしまいます。

そこで役に立つのが、一つ手前の状態を考えることです。同様の考え方はこれまで何度か登場しました。(数学の問題をプログラミングで解こう!「プラス・マイナス・ゼロ」問題解説)。n 桁の二数の足し算を考えるとき、n-1 桁のときの結果をうまく利用できないか、考えてみましょう。

そこで、関数 G(n, c, k) を新たに定義します。n 桁以下の 2 整数の足し算のうち、繰り上がりの回数が c 回であり、n+1 桁目への繰り上がりが k (0 または 1)であるものの個数を G(n, c, k) とします。

この G(n, c, k) を、n-1 桁目までの結果を使って表しましょう。次の桁への繰り上がりが ①ある場合と ②ない場合とに分けて考えます。

① 次の桁への繰り上がりがある場合を考えます。(a) 前の桁からの繰り上がりがあるときは、n 桁目の 2 数の和が 9 以上であれば次への繰り上がりが生じます。そのような可能な 2 数の組み合わせは 55 通りあります。一方、(b) 前の桁からの繰り上がりがないときは、n 桁目の2数の和が 10 以上であれば次への繰り上がりが生じます。そのような 2 数の組み合わせは 45 通りあります。したがって、下記の関係が言えます。

② 次の桁への繰り上がりがない場合を考えます。(a) 前の桁からの繰り上がりがあるときは、n 桁目の 2 数の和が 8 以下(45 通り)であれば次への繰り上がりは生じません。(b) 前の桁からの繰り上がりがないときは、n 桁目の2数の和が 9 以下(55 通り)であれば、次への繰り上がりは生じません。したがって、下記の関係が言えます。

コード例

G(n, c, k) の漸化式ができました。あとはこれを実装しましょう。実装自体は特に難しいところはないと思います。以下は python のコード例です。

N, C = map(int, raw_input().split())
g = [[0 for i in range(2)] for j in range(10)]
g[0][0] = 1

for n in range(N):
    g_next = [[0 for i in range(2)] for j in range(10)]
    for c in range(C+1):
        if c > 0: g_next[c][1] += 55*g[c-1][1] + 45*g[c-1][0]
        g_next[c][0] += 45*g[c][1] + 55*g[c][0]
    g = g_next

print g[C][0] + g[C][1]

上では実装のひと工夫として、G(n, c, k) の値を 3 重配列ではなく ck の 2 重配列で持たせ、n に関するループで次々と更新することでメモリ使用量を節約しています。(今回は n の値はたかだか 8 ですので 3 重配列の実装でも十分にクリア可能です。)

みんなのコード

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

CodeIQ「キャリー・オーバー」問題 みんなのコード

CodeIQ運営事務局より

Kawazoeさん、ありがとうございました!
現在、Kawazoeさんの最新問題が出題中です。
ぜひ挑戦してみてくださいね!

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

■関連記事

【息抜き】カードを上手く並べよう【言語不問】解答と解説... 【息抜き】カードを上手く並べよう【言語不問】 本問題は、表題のテーマで、簡単なプログラムを書くものです。 それでは以下、問題とその解答を見ていきましょう。 問題 あなたは、11から99までの、89枚のカードを持っています。問題では、横幅と高さの整数が与えられます。この横幅と高さで作られるマス...
【コードミステリ】数字に隠されたメッセージ【言語不問】解答と解説... 【コードミステリ】数字に隠されたメッセージ【言語不問】 本問題は、表題のテーマで、簡単なプログラムを書くものです。 喜屋武ちあきさんによる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 です。このときの分け方を以下に示します。 なお個々のキャンディを区別せずに扱う点に注意してください。 同...

今週のPickUPレポート

新着記事

週間ランキング

CodeIQとは

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

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

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