本履歴

購入した古本の履歴と時々プログラミング

CodeIQ

CodeIQで出題されていたマヨイドーロ問題を解いてみました。出題者は数学ガールでお馴染みの結城先生です!
使ったアルゴリズム動的計画法ですが、どういう風に私がこの解に到達したのかを時系列を追って説明したいと思います。

問題文を読んですぐに思いついたイメージはピンボールで、Xからボールが落ちてきてA,B,Cにあるフリッパーで方向が変わってYに落ちていく映像を想像しました。

最初は定石的に類似の問題を過去解いたことがあるのかどうかを自問してみました。”任意のグラフが与えられた時にグラフ上の点Pから点Qにn ステップで到達するルートの総数は隣接行列のn乗の(P,Q)成分”という事実を知っていたので、使えそうかどうか突っ込んで考えてみました。本質的には、N回反転してYに出るルートの総数が求めるものですから、

N回反転して1ステップでYに出るルートの総数+N回反転して2ステップでYに出るルートの総数+N回反転して3ステップでYに出るルートの総数+・・・

で求められそうです。ポイントは、ステップ数が多くなるにつれ、反転数も必然的に増える必要があるので、この級数の項は途中から零になるということです。このアイデアは見込みがありそうでしばらく考えていましたが、どうも反転というのをうまく表現できないことがわかってきました。というのも、隣接行列は単に繋がっているかどうかの情報しかないので、反転というのをうまく表せないんですね。
そこで、もう一度from scratchで考えてみることにしました。9回反転してYに出るルートの総数を求めることを当面の目標にします。”9回以下の”にしなかったのは、一度に扱う数が1,2,3,4・・・と増えてしまい複雑になると思ったからです。後で”以下の”で考えたほうが扱いやすいことが分かった場合は、ここに戻ってくることにします。

F(N):=N回反転してYに出るルートの総数

と定義すると、F(9)が求めるものですね。これだけでは、ただ言い換えしたにすぎないように見えますが、抽象化は大事です。さて、ここから「F(8)の答えを知っていたらF(9)は分かるだろうか?」と自問してみます。先程までの文章のまま考えていたのではできなかった進展ですね。さて、ここでparity(偶奇性)に気付きます。というのも、偶数回の反転はZに出てしまうので、Yには絶対にたどり着かないからです。そこで、Zに出るルートも一緒に考えると良さそうです。

G(N):=N回反転してZに出るルートの総数

と定義します。自問する内容は「G(8)の答えを知っていたらF(9)は分かるだろうか?」になります。G(8)の全てのルートは最後マヨイCを通りますので、そのCで反転すればYに出ますね。ただし、これがF(9)の全てを網羅しているかというとそうではないですね。というのも、G(8)には最後A->B->C->Zと辿るルートも含まれているので、Cまで来ないでその前のBで反転してYに行くこともありえますから。以上の分析から、GというZに出る総数というだけでは分類が荒くて、最後にBを通ってZに来るかどうかの情報も必要なことがわかりました。逆に、この情報があればF(9)を網羅できるでしょうか? できますね。途中の右往左往は無視すると、究極的には、Yに出るにはBで反転して来るのか、Cで反転して来るのか、に2種類しかありえません。(これを考えている時に気が付いたのは、マヨイB上で反転を繰り返すことが許されるかどうかです。つまり B->B->Bみたいなその場でクルクル向きを変えるのはありかどうか。これは問題のサンプルから無しなのがわかります。) したがって、まとめると、X を出た後の右往左往は置いておいて、途中8回反転した上最後A->Bとなるルートの総数と8回反転した上最後B->Cとなるルートの総数の合計でF(9)は計算できます!(ここでZに出ることは一旦忘れ、マヨイB,Cにとりま辿り着くルートを考えることにします!) では、”8回反転した上最後A->Bとなるルートの総数”を計算するにはどうしたらいいでしょうか? 言い換えると、X->B->◯->・・・◯->A->Bとなるルートで途中8回反転しているものですね。F,Gはもう役に立たないので捨てて、新しい関数を定義します。

H(P,Q,N):=X->B->◯->・・・◯->P->Qとなるルートで途中N回反転しているルートの総数
(P,QはA,B,Cのいずれか)

とします。問いを言い直します。H(A,B,8)はどう計算すべきでしょうか?(この問いの裏には、当然ながら、Hで再帰的に計算できると嬉しいな、という願いがこもっています(笑)) これは簡単ですね。H(B,A,7)そのものですね。つまり、7回の反転でBからAに行き、Aで8回目の反転をするパターンしかありません。それでは、F(9)を計算しようとした時の片割れのH(B,C,8)はどうでしょうか? 必ずH(A,B,8)を含むはずですね。A->Bときて、そのまま直進するパターンです。その他にも、H(C,B,7)も含みますね。C->BときてBで反転するパターンです。逆にこれら以外はありえません。あとは、マヨイドーロの対称性からH(B,A,7)やH(C,B,7)なども再帰的に計算可能です。
以上をまとめると、Hには次の漸化式があります。

H(A,B,N)=H(B,A,N-1)
H(C,B,N)=H(B,C,N-1)
H(B,A,N)=H(A,B,N-1)+H(C,B,N)
H(B,C,N)=H(C,B,N-1)+H(A,B,N)

この順番に計算することで、もれなく計算ができます。初期値はどうでしょうか? 反転0の時は、ただ右に進むだけですので

H(A,B,0)=1
H(C,B,0)=0
H(B,A,0)=0
H(B,C,0)=1

です。H(A,B,0)=1については、XをAとみなしても問題自体に影響はないので無用な複雑化を避けるためそうしています。
出力すべき数はF(N)を足し合わせたもので、F(N)はHを使って

F(N)=H(B,A,N)

です。あとはこれをコードに落とすだけです。Rubyは多次元配列の表記がうざいので、シンボルで次元を減らしています。

最終的にサブミットしたのは下記のRubyプログラムです(コメントは削除&変更)。結果的にnにでかい数があったけれどパスしました。
これがフィボナッチ数列になるのは式の形からわかるけれど、フィボナッチ数列の和が再びフィボナッチ数列になる事実が使えることは考えもしませんでした。フィボナッチ数列の単項を求めるのなら、行列のn乗をO(ln(n))で計算すればもっと速いですからね。

#!ruby

#dp[[:P2Q,i]]は、既にi回反転してある状態でPからQへ向かうルートの総数
dp={}
dp[[:A2B,0]]=1
dp[[:C2B,0]]=0
dp[[:B2A,0]]=0
dp[[:B2C,0]]=1
n=gets.to_i
1.upto(n){|i|
	dp[[:A2B,i]]=dp[[:B2A,i-1]]
	dp[[:C2B,i]]=dp[[:B2C,i-1]]
	dp[[:B2A,i]]=dp[[:A2B,i-1]]+dp[[:C2B,i]]
	dp[[:B2C,i]]=dp[[:C2B,i-1]]+dp[[:A2B,i]]
}

puts (0..n).map{|i|dp[[:B2A,i]]}.inject(:+)

問題と解説
https://codeiq.jp/magazine/2015/12/35521/