読者です 読者をやめる 読者になる 読者になる

本履歴

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

「の」の字形の無限に循環する配列のk番目

K-th Value of Japanese Hiragana Character "の"-like Infinitely Circulating Array

コンピュータは有限しか扱えないので前の状態から次の状態が決まる系は最終的に必ず循環します。そんな循環する状態列のk番目をここでは求めたいと思います。例えば、みんな大好きフィボナッチ数列1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...で純粋数学的にはこのまま増大していくのですが、有限しか扱えないコンピュータでは10^9+7で割った余りとかにして32bitに収まるよう妥協します。ここでは試しに11で割った余りにして最初の項から見てみると1, 1, 2, 3, 5, 8, 2, 10, 1, 0, 1, 1, 2, 3, 5, 8, 2, ...となり、すぐに循環してしまいました。フィボナッチ数列は定義から前の2項の和で次の項が決まるので、実際は数列内に1, 1パターンが2回目に出てきた所で計算(2項を足して11で割る)を打ち切って、それまで計算した結果を使ってk番目の値は簡単に分かります(これを後で見ます)。一般的には鳩の巣原理 - Wikipedia から、11*11+1番目まで計算すれば必ず既に循環していると言えます。ただし、10^9+7で割る例の場合は、最悪(10^9+7)^2+1番目まで計算しないと循環しない可能性があるので、有名な行列のpowmodを使うべきです。前述のフィボナッチ数列の例では一番最初に戻ってしまいましたが(円環)、一般的には途中の状態に戻ることが多く、その場合、自分は配列が「の」の形に似ているなあと常々感じています(一番最後に戻る=同じ状態が永遠と続く場合は「の」の円が潰れて「つ」になってしまいますが(笑))。英語でなんと表現するんでしょう? 似たような形のアルファベットはbやd, e,, p, qって結構ありますね。実際のプログラムは簡単で、どこに戻るのかで場合分けをすればOKです。ret_ptが「の」の字の合流点で、円周長がsize - ret_ptです。

#!ruby
#”の”の字型無限循環配列のk番目を求める

#ary: 循環配列
#ret_pt: 配列最後まで行った時にどこに戻るか
#k: 求める番目、当然配列のサイズより大きいことが予想される
#0-indexed
#O(1)

def no_at(ary, ret_pt, k)
    size = ary.size
    return ary[k] if k < size
    return ary[k % size] if ret_pt == 0
    return ary.last if ret_pt == size - 1
    k -= ret_pt
    r = k % (size - ret_pt)
    ary[ret_pt + r]
end

フィボナッチ数列の例で使うときはno_at([1, 1, 2, 3, 5, 8, 2, 10, 1, 0], 0, 1000)でもいいですしno_at([1, 1, 2, 3, 5, 8, 2, 10, 1, 0, 1], 1, 1000)でもOK。ではどうやって循環していることを調べるかについてですが、これはRubyだと現在の状態をハッシュに入れておけば二度目に出てきた時判別できます。オススメなのがハッシュの値を配列のindexにする方法。Ruby likeなpseudo codeだと

S = 系の初期状態
H = Hash.new
A = Array.new
Until H[S]
  A << S
  H[S] = A.size-1 #配列A内の状態Sの位置
  S = NextState(S)
End

Print no_at(A, H[S], k)

で計算量はO(|A|)すなわち状態の総数になります。したがってこれを使うときは状態の場合の数がどのくらいになるか事前に見積もることが必要です。 実際、mod 11フィボナッチ数列の最初の15項目を上記に当てはめて求めてみると、

#!ruby
M = 11
s = [1, 1]
h = Hash.new
a = Array.new
until h[s]
    a << s
    h[s] = a.size - 1
    s = [s.last, (s.first + s.last) % M]
end

15.times{|k|
    p no_at(a, h[s], k)
}

# [1, 1]
# [1, 2]
# [2, 3]
# [3, 5]
# [5, 8]
# [8, 2]
# [2, 10]
# [10, 1]
# [1, 0]
# [0, 1]
# [1, 1]
# [1, 2]
# [2, 3]
# [3, 5]
# [5, 8]

となりうまく行ってます。ちなみに、今回は純粋に状態を返していますのでフィボナッチ数列の実際の項を求めるには、リターン値の加工が必要です。このようなのの字ループですが、応用例は他にも 線形合同法 - Wikipediaなど枚挙にいとまがないくらいです。 以下、この考え方が使えるオンラインジャッジ問題の二例です。

Infinity Maze

例えば、Infinity Maze | Aizu Online Judgeでは、ロボットが与えられた迷路上で直進し壁にぶつかったら右に向きを変えてまた直進ということを繰り返していく時のL歩進んだロボットの最終位置と向きが問われますが、ロボットの迷路上の位置と向きが与えられればそれ以降の動きが完璧に決まるので、そのうちロボットは循環することが分かります。つまり「の」の字メソッドが使えます。状態数は迷路のサイズ(100*100)とロボットの向き(4通り)の組み合わせで高々40,000となり、Rubyでも十分間に合います。

Google Code Jam Qualification Round 2010 C. Theme Park

Dashboard - Qualification Round 2010 - Google Code Jam

こちらの問題も同じ考えが適用できます。問題の趣旨は、ジェットコースターに複数グループ(Max 1,000)がキューになって並んで居て、乗り終わったグループは再び整列することを繰り返す時に一日に何人がジェットコースターに乗るかを答えます。ジェットコースターは一日108回走りキャパシティは109で、各グループはグループメンバー全員が乗れない場合は次のを待ちます。これもキューの最初のグループが決まればその後の状態は決まるということと状態数が1000であることから、高々1000+1回シミュレーションすれば「の」の字無限ループに入るはずです。実際、問題のサンプルにもあるグループ[1, 4, 2, 1]キャパ6、4回運転の例を取ってみると、

[1, 4, 2, 1] =>5人
[2, 1, 1, 4] =>4人
[4, 2, 1, 1] =>6人
[1, 1, 4, 2] =>6人
[2, 1, 1, 4]

となり無事循環しました(ちなみに総搭乗者数は21)。この問題が少し難しいのは108回目の状態(どのグループが一番最初に並んでいるか)ではなく、各状態に付随する数値の総和を求めることです。これもno_atメソッドを少し変形するだけで求められます。スタートからのの字の合流点までとクルクル回転するところと最後のところの3パターンです。実際はスタートから合流点と最後のところは一緒にできるので2パターンの場合分けですみます。メソッドno_sumは各配列に対し1回しか呼ばれないのでinjectしていますが、何回も呼ばれる場合は総和計算をDPにすべきです。

#!ruby
#”の”の字型無限循環配列のk番目までの総和を求める
def no_sum(ary, ret_pt, k)
    size = ary.size
    return ary[0..k].inject(:+) if k < size
    return (k / size) * ary.inject(:+) + ary[0..k % size].inject(:+) if ret_pt == 0
    return ary.inject(:+) + (k - size + 1) * ary.last if ret_pt == size - 1
    k -= ret_pt
    q, r = k.divmod(size - ret_pt)
    ary[0..ret_pt + r].inject(:+) + q * ary[ret_pt..size - 1].inject(:+)
end

これを用いてTheme Parkを解いてみると、下記のようになりました。ラージも十分通ります。注意点は合計用の配列bを用意しているのと、状態がどのグループが先頭にいるかで決まるためindex付きの配列groupを用意しているのと、全部のグループが乗車したらそれ以上乗車を打ち切るようにrotate_numがnを超えないように監視しているのと、0-indexedにするためr-1にしている所になります。本質的にはpseudo codeそのままなのがお分かりいただけるはずです。

#!ruby
def solve(r,k,n,g)
    group = g.each_with_index.to_a
    s = 0
    h = Hash.new
    a = Array.new #for state
    b = Array.new #for summation
    until h[s]
        a << s
        h[s] = a.size - 1
        passenger = 0
        rotate_num = 0
        while passenger + group.first.first <= k && rotate_num < n
            passenger += group.first.first
            group.rotate!(1)
            rotate_num += 1
        end
        b << passenger
        s = group.first.last
    end

    no_sum(b, h[s], r - 1)
end

以上をまとめると、前の状態から次の状態が決まる系では「の」の字型循環になり、そのk番目の状態(やk番目までの和)はループする箇所をdivやmodすることにより状態総数の計算量で求められます。 個人的には、循環は仏教の輪廻的な考え方なので好きです。この宇宙も有限個の原子で出来ているならばそのうち「の」の字循環することが分かります。えっ?もう何回も循環してる!?

補足

知り合いから「の」でなく「6」では?と言われた。確かに書き順からしてそうだ(笑)

Identifies mirrored and rotated one

したがって面白くするため、回転・鏡像を含めて同一視した場合にどのくらいになるか手で数えてみた。なんとなく偶数になると思っていたが、N=4の場合は7という数字が出てきて不思議な感じ。これは配置によって回転・鏡像変換8通り全てが異なる順列になる場合や1234=4321のように2つしか同一視できないなど結構複雑だ。そこで早速プログラムを組んでカウントしてみた。1,1,2,7,23,115まで求めて後はOEISに突っ込めばやはり誰かが既に求めていた(https://oeis.org/A000903
この数列に関する面白い結果は特になさそうでちょっと残念。

#飛車を相互にアタックしないように配置するパズル
#回転鏡像含め同一視した中でいくつの場合があるか数える
#0-indexed
#O(N!)

def rotate(a)
	a.each_with_index.sort_by(&:first).reverse.map(&:last)
end

def mirror(a)
	table=[*0...a.size].reverse.each_with_index.to_a
	a.map{|v|table[v]}
end

N=6
count=0
h={}
[*0...N].permutation(N).each{|perm|
	next if h[perm]
	count+=1
	until h[perm]
		h[perm]=true
		perm=rotate(perm)
	end
	perm=mirror(perm)
	until h[perm]
		h[perm]=true
		perm=rotate(perm)
	end	
}

p count

N Rooks = N!

チェスにハマったので、8 Queensのカウンターパート的8 Rooksを考えてみた。チェスでRook(ルック、lookと発音は違う)は将棋で言うところの飛車の動きをする駒で、それを8*8のチェスボード上に互いに攻撃しあわないよう置くことを考えることになる。これは少し考えれば明らかなように順列そのままである。すなわち、最初の列に置けるパターンは8通り。次の列は最初に置いた駒の行を外して7通り(以下同)となって順列だ。クイーンの斜めの効きがないため非常にシンプルになる。

Faster DP Implementation of Integer Partition Function with the Complexity O(N^2)

そこで色々調べた所、蟻本にO(N^2)の方法が載っている事がわかって一件落着。こちらもDPだけど、分割する数を取るのが違う点。

DP[n,m]=nをm個以下で分割するときの総数とするとDP[n,m]=DP[n,m-1]+DP[n-m,m]

nをm個以下の整数の和にするときに0も含めて考えているのがナルホド。そして、0を含むものと含まないもので分けて、うまく次元が低い処理にそれぞれ帰着できているのがすごい(小並感)

#!ruby
M=1000000007
def integer_partition_faster(n)
	dp=Array.new(n+1){Array.new(n+1,0)}
	dp[0][0]=1
	1.upto(n){|j|
		0.upto(n){|i|
			if i-j>=0
				dp[i][j]=(dp[i][j-1]+dp[i-j][j])%M
			else
				dp[i][j]=dp[i][j-1]
			end
		}
	}
	dp[n][n]
end

さて、実際の両者のコードをよく眺めると、結構似てる気がしませんか? 意図的に添字を同じにしたのもあるけど。というわけで、両アルゴリズムで使われている変数のdpを比べてみるとなんと驚き(ドラムロールオン♪)、中身が全く一緒になっているじゃありませんか!! Curiouser and curiouser. Don't you think so?

整数の分割って数論の一分野になっていますが、実は面白い定理が成り立つのです:

整数 n を分割したときの成分の数が k 個以下になるような分割の総数は、成分が k 以下の整数となるような n の分割の総数に等しい。

はい、そのまんまですね(笑)。なんか競プロの練習を通じてこの定理を証明したっぽい感じがしましたので、熱が冷めないうちにblog記事にしてみました。
その名もズバリ整数の分割って本に証明とかヤング図形との対応とかその他諸々興味深いことが詳しく載ってたはず。

整数の分割

整数の分割

Naive DP Implementation of Integer Partition Function with the Complexity O(N^3)

整数を分割したい病に患ってしまった。見る整数はなんでも、4=1+1+1+1=1+1+2=1+3=2+2のように分割してしまう恐ろしい病気だ。ちなみに4の場合の分割数は5である(自身も含める)。Wikipedia(https://en.wikipedia.org/wiki/Partition_(number_theory) )を読んでいた所、この数を計算するアルゴリズムとして次のようなものが載っていた:

補助関数 p(n,m)をm以下の数の和でnを表現する場合の数とするとp(n,n)が求めるもので、p(0,i)=1、p(i,j)=p(i,i) where i

これをそのままコードに落とすとO(N^3)でとても遅い。遅いアルゴリズムは泣きたくなる。

#!ruby
M=1000000007
def integer_partition_naive(n)
	dp=Array.new(n+1){Array.new(n+1,0)}
	dp[0][0]=1
	1.upto(n){|k|dp[0][k]=1}

	1.upto(n){|i|
		1.upto(n){|k|
			if k>i
				dp[i][k]=dp[i][i]
				next
			end
			1.upto(k){|j|
				dp[i][k]=(dp[i][k]+dp[i-j][j])%M
			}
		}
	}
	dp[n][n]
end

Pure Implementation of Dijkstra's Shortest Path Algorithm with Priority Queue in Ruby

プログラム言語 Ruby での純粋ダイクストラ最短経路アルゴリズム(優先順位付きキュー利用)です。O(m*log(n))の実行時間です(n:ノード数、m:辺の数)。
外部ライブラリなどに依存していないため、このままコピペすれば競技プログラミングで使えると思います。Ruby1.9.3..Ruby2.3.0で動きました。1.9.3は2.3.0の1.8倍時間がかかりました。
一応、AOJのGraph II - Single Source Shortest Path II(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_12_C)とAtCoderのABC#035 D - トレジャーハント(http://abc035.contest.atcoder.jp/tasks/abc035_d)は通ったので、Rubyのバージョンが高い&&寛容(?!)なオンラインジャッジ(通常時間制限の数倍余裕くれるところ)では通ると思います。しかし、C++なんかと同じタイム制限のところではまず通らないと思います。やはり十数倍..数十時間がかかるようです。

利用上の注意点は、edges, costs共に0-indexedに加工して下さい。問題文で町に番号が1..nと割り振られーとかある場合に注意が必要。またアルゴリズムの性質上負のコストがあるとうまく動きません。プログラムはsから到達できる全ノードを巡った後最小コスト配列を返しますが、目的地がeと明確になっているのなら、visited[e]=trueになったら即終了したほうが速い。競技プログラミングの性質上、凶悪入力にも打ち勝たないといけないのであまり意味はないかもですが。
precursorには、アンコメントの後、最小コストのルートの1個前のノードが入ります。e=precursor[e] while e で後ろから前に辿れます。

以上です。よろしくお願い致します。

#!ruby

#Last Updated at 04/06/2016
#最短経路問題をダイクストラwith優先順位付きキューアルゴリズムで解く
#入力:
#edges: nノードの隣接リスト(0-indexed) e.g. [[1,2,3],[5],[0,1],...] means
# node 0からの辺はnode 1,2,3へ出ている、node 1からはnode 5のみ等々
#costs: コスト(辺の長さなど)、costs[x][y]で正数を返せばOK。
#s: 開始点。0..n-1
#出力:
#sからの最小コストのリスト dijkstra(edges,costs,s)[e]でs-e間の最小コスト
#到達出来ない点はINF
#経路を知りたい場合はprecursorのアンコメントする。precursor[k]でnode kの前のノードがわかる

INF = 1 << 60 #プログラム簡易化のため利用。全コスト和より大きい値にする

#O(m*log n) where m:辺の数
def dijkstra(edges, costs, s = 0)
	#初期化
	n = edges.size #ノード数
	node_to_pq_id = Array.new(n, nil) #nodeとpq.push時に割与えられたkeyの対応を管理
	#precursor = Array.new(n,nil)
	d = Array.new(n, INF) #sから別ノードまでの(これまで分かった)最短コスト
	d[s] = 0
	pq = PriorityQueue.new
	edges[s].each{|u|
		id = pq.push(Node.new(costs[s][u], u))
		d[u] = costs[s][u]
		node_to_pq_id[u] = id
		#precursor[u] = s
	}
	visited = Array.new(n, false) #既に訪れたか?
	visited[s] = true

	#本体処理
	until pq.empty?
		min = pq.pop
		cost,v = min.cost, min.node
		visited[v] = true
		d[v] = cost
		edges[v].each{|w|
			next if visited[w]
			next if d[w] <= cost + costs[v][w]
			#precursor[w] = v
			d[w] = cost + costs[v][w]
			#ノードwまでの冗長だったコストをよりお得なv経由コストにPQ内で変更
			if node_to_pq_id[w]
				pq.change_key(node_to_pq_id[w], Node.new(d[w], w))
			else
				#PQに初めてノードを入れる場合
				id = pq.push(Node.new(d[w], w))
				node_to_pq_id[w] = id					
			end
		}
	end
	d
	#[d, precursor]
end

#PQ用データ構造、コード簡易化のため
class Node
	attr_reader :cost, :node
	def initialize(cost, node)
		@cost = cost
		@node = node
	end

	def <= other
		@cost <= other.cost
	end

	def < other
		@cost < other.cost
	end

	def >= other
		@cost >= other.cost
	end

	def > other
		@cost > other.cost
	end
end

#Last Updated at 04/06/2016

#優先順位付きキュー
#ストアするデータは<=>で比較可能でなければならない
#小さい順か大きい順かは”符号を逆に”コメント箇所を変更
class PriorityQueue
  attr_reader :elements

  def initialize
    @elements = [nil] #ダミー。1-indexedにするため
    @position = {} #idのデータが@elementsのどこにあるかindexを返す
    @id = 0 #付与するid。1ずつインクリメント
  end

  #PQにデータを追加。付与されるidはchange_keyするときに指定する
  #つまり3を2回追加してもidは別になる
  #change_keyしない時は@position,@idの処理は全て不要
  #O(log n)
  def add(element)    
    @id += 1
    @elements << [element, @id]
    @position[@id] = size
    bubble_up(size)
    @id
  end

  #最小(大)値をPQから取り出し返す
  #O(log n)
  def pop
    exchange(1, size)
    max = @elements.pop
    bubble_down(1)
    max.first
  end

  #id(add時に付与される整数)による値の変更
  #値では動作できない(同じ値が入ることがあるため)
  #成功:self、失敗:nil
  #O(log n)
  def change_key(target_id, new_element)
    index = @position[target_id]
    return nil unless index
    if @elements[index].first <= new_element #符号を逆に
      @elements[index][0] = new_element
      bubble_down(index)
    else
      @elements[index][0] = new_element
      bubble_up(index)
    end
    self
  end

  #ストアされているデータ数
  def size
    @elements.size - 1
  end 

  def empty?
  	size == 0
  end

  alias :push :add
  alias :<< :add
  alias :length :size
private

  def bubble_up(index)
    parent_index = (index / 2)

    return if index <= 1
    return if @elements[parent_index].first <= @elements[index].first #符号を逆に

    exchange(index, parent_index)
    bubble_up(parent_index)
  end

  def bubble_down(index)
    child_index = (index * 2)

    return if child_index > size

    not_the_last_element = child_index < size
    left_element = @elements[child_index]
    right_element = @elements[child_index + 1]
    child_index += 1 if not_the_last_element && right_element.first <= left_element.first #符号を逆に

    return if @elements[index].first <= @elements[child_index].first #符号を逆に

    exchange(index, child_index)
    bubble_down(child_index)
  end

  def exchange(source, target)
    @position[@elements[source].last], @position[@elements[target].last] = target, source
    @elements[source], @elements[target] = @elements[target], @elements[source]
  end
end

if __FILE__ == $0
  n = 120000
  m = 500000
  bridged = {}
  costs = Array.new(n){Hash.new}
  edges = n.times.map{|i|
    if i == 0
      costs[i][1] = i
      bridged[[0, 1]] = true
      [1]
    elsif i == n - 1
      costs[i][n - 2] = n - 2
      bridged[[n - 1, n - 2]] = true
      [n - 2]
    else
      costs[i][i - 1] = i - 1
      costs[i][i + 1] = i
      bridged[[i, i - 1]] = true
      bridged[[i, i + 1]] = true
      [i-1, i+1]
    end
  }

  m.times{
    i, j = rand(n), rand(n)
    next if i == j
    next if bridged[[i, j]]
    edges[i] << j
    costs[i][j] = rand(n)
  }

  p dijkstra(edges, costs).last
end

ruby-prof

 %self      total      self      wait     child     calls  name
 10.76      7.970     3.695     0.000     4.275  1930414   PriorityQueue#exchange
 10.60      3.642     3.642     0.000     0.000 18678231   Array#[]
  6.42      3.806     2.206     0.000     1.599  3920171   PriorityQueue#size
  5.62      2.239     1.931     0.000     0.309  4960817   Hash#[]=
  5.08      4.941     1.744     0.000     3.197        3   Integer#times
  4.92      2.387     1.689     0.000     0.698  3750646   Node#<=
  4.48      1.540     1.540     0.000     0.000  7557191   Array#first
  2.98      1.023     1.023     0.000     0.000  4469026   Array#[]=
  2.77      4.905     0.953     0.000     3.952   120000   Array#each
  2.68      0.922     0.922     0.000     0.000  4520167   Fixnum#-
  2.48      0.851     0.851     0.000     0.000  4465190   Fixnum#<=
  2.31      0.793     0.793     0.000     0.000  3920172   Array#size
  2.24      0.770     0.770     0.000     0.000  3860829   Array#last

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/