結城浩の「マヨイドーロ問題」問題解答 ( CodeIQ ) 前編

CodeIQ 数学

はじめに

CodeIQというところで、結城さんのプログラミング問題に解答しましたので、そのネタばれです。

codeiq.jp

問題

標準入力Lに対し、次の図にあるような図で、Xを出てYに辿り着く方法が何通りあるかを出力します。
ただし、Zには到着せず、かつ方向転換できるのはA,B,Cの地点のみ、その回数の上限はLとします。
f:id:ange1:20151217100226p:plain

数学的なアプローチ

方針

折り返し点毎に規則性を整理し、漸化式を導くことを目指します。

規則性

まず、「Xから出発」は、「AからZ方向に出発」と置き換えてもと同じです。
f:id:ange1:20151217100452p:plain

そうしたうえで、「AからZ方向に出発」「BからZ方向に出発」の2ケースを考えてみます。
※「CからZ方向に出発」はすぐにZについてしまうため除外します。

  • Aから出発した場合、
    • A→B(反転)→A→Y
    • A→B→C(反転)→B→A→Y
    • A→B(反転)→A(反転して再出発)
    • A→B→C(反転)→B→A(反転して再出発)
    • A→B→C(反転)→B(反転して再出発)
  • Bから出発した場合、
    • B→C(反転)→B→A→Y
    • B→C(反転)→B→A(反転して再出発)
    • B→C(反転)→B(反転して再出発)

図を見た方が早いですね。
f:id:ange1:20151217100413p:plain

「再出発」というのは、反転回数の上限を2減らして再帰的に扱うことができますから、 「Aから出発」「Bから出発」それぞれの、反転回数上限Nに対する場合の数をA_{N},B_{N}とすると、

  • A_{0}=B_{0}=0,A_{1}=2,B_{1}=1
  • A_{N}=2A_{N-2}+B_{N-2}+2\ ( N\geq 2 )
  • B_{N}=A_{N-2}+B_{N-2}+1\ ( N\geq 2 )

という漸化式を立てることができます。

漸化式の整理

ここで、Yに到着するためには、使える反転回数は奇数に限られますので、N が偶数の場合1回分が無駄になります。 そのため、N の代わりに、ほぼ半分の値である n=\lfloor\frac{N+1}{2}\rfloor を用いても問題ないと言えます。

改めて、

  • A_{N}=a_{n}, B_{N}=b_{n}\ ( 但し n=\lfloor\frac{N+1}{2}\rfloor )
  • a_{0}=b_{0}=0
  • a_{n}=2a_{n-1}+b_{n-1}+2\ ( n\geq 1 )
  • b_{n}=a_{n-1}+b_{n-1}+1\ ( n\geq 1 )

と整理することができました。

更に、漸化式の定数項を

  • (a_{n}+1)=2(a_{n-1}+1)+(b_{n-1}+1)
  • (b_{n}+1)=(a_{n-1}+1)+(b_{n-1}+1)

と吸収させると、行列・ベクトル積による表現に変換できます。
すなわち、

  • \begin{pmatrix}a_{n}+1 \\ b_{n}+1 \end{pmatrix}= \begin{pmatrix}2 \ \ 1 \\ 1 \ \ 1 \end{pmatrix} \begin{pmatrix}a_{n-1}+1 \\ b_{n-1}+1 \end{pmatrix}

これにより、一般項は次のように表せます。

  • \begin{pmatrix}a_{n} \\ b_{n} \end{pmatrix}= \begin{pmatrix}2 \ \ 1 \\ 1 \ \ 1 \end{pmatrix}^{n} \begin{pmatrix}a_{0}+1 \\ b_{0}+1 \end{pmatrix}- \begin{pmatrix}1 \\ 1 \end{pmatrix}

答え

最終的に求めるのは、「Aを出発」の場合の数、A_{L}です。
そのため、

  • A_{L}=a_{n}= \begin{pmatrix}1\ \ 0\end{pmatrix} \begin{pmatrix}2 \ \ 1 \\ 1 \ \ 1 \end{pmatrix}^{n} \begin{pmatrix}1 \\ 1 \end{pmatrix}-1\ ( 但し n=\lfloor\frac{L+1}{2}\rfloor )

を計算することで答えが導けます。

実装

提出版

提出したコードは、上記行列での計算を、Rubyのmatrixで実装したものです。

require 'matrix'
puts (Matrix[[2,1],[1,1]]**((gets.to_i+1)/2)*Vector[1,1])[0]-1

まんまですね。
なお、Lの値として最大2015が用意されていました。解はLに対して指数的に増加するため、C/C++等では標準の整数型では到底収まりません。…がそこはRuby、自動的に任意制度整数として計算してくれますので楽ちんです。

Ruby→Brainf**k→Cへの移植

当初は行列計算版で終わりにしようと思ったのですが、全国10万人(希望的観測)のBrainf**kファンの皆様の声にお応えするため、考えてみました。
流石に行列計算を移植するのは大変ですが、別の規則性から攻めることができます。

  • (p_{0},q_{0})=(2,1),(p_{1},q_{1})=(5,3),(p_{2},q_{2})=(13,8),\cdots に対して答えは q_{\lfloor\frac{L+1}{2}\rfloor}-1
  • q_{n}=p_{n-1}+q_{n-1},\ p_{n}=p_{n-1}+q_{n}

つまり、次のような単純な足し算だけで実装できるわけです。
※もっと短い書き方もできますがまあ ( q じゃなくて p を使う方が分かり易いような気も… )

p,q=2,1;1.step(gets.to_i,2){q+=p;p+=q};p q-1

それであれば、Brainf**kでも十分に実装できます。具体的にはこちら。コメント等除くと437文字で済んでしまいます。

Brainf**kで実装できるなら、Cでも実装できるはずでint型の上限の悩みなど嘘のように忘れることができます。ということで移植したのがこちらになります。

一旦まとめ

  • 行列計算で答えは求められます
  • 単純な足し算の繰り返しで処理できるので、Brainf**kでも実装できます
  • Brainf**k版を移植するとCでも簡単

ちょっと書ききれなくなったので、後編へ続く