ガジェット通信

見たことのないものを見に行こう

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

DATE:
  • ガジェット通信を≫

問題のおさらい

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

レベル 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さんの最新問題が出題中です。
ぜひ挑戦してみてくださいね!

カテゴリー : デジタル・IT タグ :
CodeIQ MAGAZINEの記事一覧をみる ▶
  • 誤字を発見した方はこちらからご連絡ください。
  • ガジェット通信編集部への情報提供はこちらから
  • 記事内の筆者見解は明示のない限りガジェット通信を代表するものではありません。

TOP