CodeIQ MAGAZINECodeIQ MAGAZINE

数学の問題をプログラミングで解こう!「トライアングル・メイズ」問題解説

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

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

「数学の問題をプログラミングで解こう!」シリーズ。
迷路を最短距離でクリアするたどり方の数を求める問題でした。
一見、複雑な迷路ですが、「一つ前の状態を考える」という原則にのっとって考えれば糸口が見つけられます。

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

問題のおさらい

次のルールで生成される迷路を考えます。

レベル 1 の迷路から始めましょう。レベル 1 の迷路を M1 と呼びます。M1 は、3 つの点を L の字の形につないだものです。左上の点がスタートで、右下の点がゴールです。

レベル 2 の迷路 M2 は、M1 を 3 つつなげて作ります。M1 を 1 つ置き、さらにその上と右に 1 つずつ M1 をつなげたものです。左上の点がスタートで、右下の点がゴールです。

レベル 3 の迷路 M3 は、M2 を 3 つつなげて作ります。M2 を 1 つ置き、さらにその上と右に 1 つずつ M2 をつなげたものです。左上の点がスタートで、右下の点がゴールです。

以降同様に、レベル k の迷路 Mk を、レベル k-1 の迷路 Mk-1 を 3 つつなげることで定義します。

さて、この迷路を、点と線をたどってスタートからゴールまで着く方法を考えます。
自然数 n に対し、迷路 Mn を最短距離でゴールするたどり方の数を F(n) と定義します。

例えば F(1) = 1,F(2) = 2 です。

同様に、F(3) = 6,F(4) = 42 です。
さらに、F(10) を 1000003(=106+3) で割った余りは 998593 となることが確かめられます。

標準入力から、自然数 n(1 ≦ n ≦ 108)が与えられます。
標準出力に F(n) を 1000003 で割った余り を出力するプログラムを書いてください。

方針

このシリーズでも何回か登場した考え方「一つ前の状態を考える」が有効です(数学の問題をプログラミングで解こう!「プラス・マイナス・ゼロ」問題解説)。レベル n の迷路 Mn のクリアの仕方が、レベル n-1 の迷路 Mn-1 のクリアの仕方とどのように関係するかを考えましょう。

下図は、Mn のたどり方を示したものです。大きく分けて、点 A を経由するルートと、点 B と点 C を経由するルートの 2 通りが存在します。

点 A を経由するルートの場合、まず、スタートから点 A までのたどり方が F(n-1) 通りあります。また、点 A からゴールまでのたどり方が F(n-1) 通りあります。したがって、このルートでの行き方は、全部で F(n-1)2 通りです。

点 B と点 C を経由するルートの場合、スタートから点 B までのたどり方が 1 通り、点 B から点 C までのたどり方が F(n-1) 通り、点 C からゴールまでのたどり方が 1 通りです。したがって、このルートでの行き方は、全部で F(n-1) 通りです。

以上から、Mn のたどり方 F(n) を、F(n-1) を用いて表すことができます。

漸化式はできた! だけど単純な実装ではうまくいかない

さて、F(n-1) を使って F(n) を表すことができました。F(1)=1 から始めて、次々と F(2), F(3), … を求めていけばよさそうです。

こんなコードが考えられます。

n = input()
f = 1
for i in range(2, n+1):
    f = (f * (f+1)) % 1000003
print f

ひとまずこれで正しい答えが得られます。ただ、今回は n が最大で 108 です。このコードでは n 回程度の計算を要します。実行時間がかかりすぎて、1 秒の制限時間内で答えを出すことはできません。もうひとひねりが必要です。

ここで役に立つのが、周期性を利用する という考え方です。この考え方は以前の記事でも紹介しました(数学の問題をプログラミングで解こう!「エース・ナンバー」問題解説)。F(n) はたかだか 1000003 通りの値しか取り得ず、また、一つ前の F(n-1) の値のみによって決まります。したがって値に周期性があるはずです。その周期のパターンが分かれば、わざわざ 108 のような大きな回数の計算を行わなくても、ずっと手前の値を計算するだけで済むのです。

それでは、周期のパターンを見つけるコードを書いてみましょう。基本的には、上のコードと同じように、F(n) の値を次々と計算していきます。そのときに、n と F(n) の組を覚えておきます。辞書型が使える言語なら、キーに F(n)、バリューに n の値を入れるとよいでしょう。

f, k = 1, 1
d = dict()
while True:
    if d.has_key(f):
        offset, period = d[f], k - d[f]
        print 'F(n) は, n = ' + str(offset) + ' 以降,',
        print '周期 ' + str(period) + ' でループする'
        break
    d[f] = k
    f = (f * (f+1)) % 1000003
    k += 1

実行結果は次の通りです。

F(n) は, n = 214 以降, 周期 955 でループする

つまり、こういうことです。

n の値がどれだけ大きくとも、214 を超えた分を 955 で割って余りを出せば、ずっと小さい値に帰着させることができるのです。コード例を以下に示します。(上のコードと合わせて一つにする方がコード的にはイケてますが、こだわらなくてもOKです。)

n = input()
offset, period = 214, 955
if n >= offset:
    n = (n - offset) % period + offset
f = 1
for i in range(1, n):
    f = (f * (f+1)) % 1000003
print f

みんなのコード

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

CodeIQ「トライアングル・メイズ」 みんなのコード

CodeIQ運営事務局より

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

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

■関連記事

【謎解きプログラム】条件に当てはまる文字列は?【正規表現】解答と解説... 【謎解きプログラム】条件に当てはまる文字列は?【正規表現】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 「2...
数学の問題をプログラミングで解こう!「クロッシング・ワード」問題解説... 問題のおさらい クロスワードの盤面では、格子状のマス目に白マスまたは黒マスを配置します。 以下は、縦 3 個×横 4 個のマス目に白マス・黒マスを配置する例です。 白マス・黒マスの配置には次のルールがあります。 黒マスによって白マスの領域が分断されてはならない。 黒マスが縦・横に連続し...
【謎解きプログラム】乱数で発生する数値は?【組み合わせ】解答と解説... 【謎解きプログラム】乱数で発生する数値は?【組み合わせ】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 「24...
「放物線とマス目の関係」問題の解答と解説... table.nabe{ margin-left:30px; } .nabefloat{ float:right; } table.nabe td, table.nabe th{ padding:3px; } table.nabe th{ ...
【謎解きプログラム】データをバイナリで見てみよう【バイナリ】解答と解説... 【謎解きプログラム】データをバイナリで見てみよう【バイナリ】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 「...
数学の問題をプログラミングで解こう!「プライム・ペア」問題解説... 問題のおさらい 自然数 k に対し、1 から k までの自然数のうち k と互いに素なものの個数を F(k) と定義します。 (F(k) はオイラーのφ関数とも呼ばれています。参考:オイラーのφ関数(Wikipedia)) 例えば F(12)=4 です。1 から 12 のうち 12 と互いに素...

今週のPickUPレポート

新着記事

週間ランキング

CodeIQとは

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

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

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