「トライアングル・メイズ」問題解答 ( CodeIQ )

CodeIQ 数学

はじめに

CodeIQというところでプログラミング問題「トライアングル・メイズ」に解答しましたので、ネタバレです。

codeiq.jp

問題

今回は次のような問題でした。

  • 次の図のように、1段階毎に、前の段階の迷路を3つつなげていくような迷路に対して、n段階目の迷路のスタートからゴールまでの最短経路が何通りあるかをF(n)で表すとき、入力 n に対してF(n)を1000003 で割った余りを出力する。

https://codeiq.jp//sites/default/files/answer_ready/2833/1.png

なお、問題の制約は、$1\le n\le 10^{18}$ となっています。なので、計算量のオーダーが$O(n)$行くようだとTLE必至です。

解説

次のRubyのコードを提出しました。

M=1000003
n=gets.to_i
m=[1]
h={1=>1}
x=1
2.upto(n){|i|
  x=x*(x+1)%M
  if b=h[x]
    x=m[(n-i)%(i-b)+b-1]
    break
  else
    m.push(x)
    h[x]=i
  end
}
puts x

次の図は、4段階目の迷路の例ですが、

f:id:ange1:20160930001017p:plain

  • スタート→b地点→ゴールという経路
    それぞれが3段階目の迷路を辿る経路のため、$F(3)^2$通り
  • スタート→a地点→c地点→ゴールという経路
    スタート→a地点、c地点→ゴールは1本道のため、実質3段階目の迷路と同じ、$F(3)$通り

ということで、$F(4)=F(3)^2+F(3)$ だと分かります。

ここから、$F(n+1)=F(n)\times(F(n)+1)$という漸化式が立てられるため、基本的にループで漸化式を回していきます。

ただし、今回は mod 100003 での値なので、必ず周期的に同じ計算結果が出てくるようになります。
そこで、値の重複を検出した時点で周期を割り出し、n での値が、出現済みの値のどれになるかを判断します。
※このループ検出せずに漸化式を回すだけだと、計算量$O(n)$になって死にます。

終わりに

漸化式が直ぐ出たので、方針は立てやすかったのですが…。これ、他にやりようがあるんでしょうか…。