https://codeiq.jp/magazine/2015/12/35521/ の解答

mayoidoro.py

# 方針（詳しく説明するのは大変なので、概略だけ）
#
# ちょうどN回反転して出るルートの総数を足し合わせれば良い。
# Nが偶数の時は0なので、奇数の時を考える。
#
# N = 2M - 1回反転するときのルートの総数は、
# Mを正の整数に順列分割（？）する総数に対応づけることができる。（方法は省略）
# 具体的には、問題は次のもの。
#
# 問題
# Mを正整数の和に分割し、
# その和の順序が違うものは、別のものとして数えたときの総数を求めよ。
# さらに、今1は1a, 1bの2種類あるものとする。
#
# 例えば、M=1のときは、
# 1a, 1b
# の2通り。
# M=2のときは、
# 1a + 1a, 1a + 1b, 1b + 1a, 1b + 1b, 2
# の5通り。
#
# このうち、和が1aから始まるものの総数をa[M],
# それ以外から始まるものの総数をb[M]とすると、
# 次の漸化式が成り立つ。
# a[1] = b[1] = 1
# a[i+1]=a[i] + b[i]
# b[i+1]=a[i] + 2b[i]
# これをコードにしたものがこの解答。
# （おそらく整理すればフィボナッチ数になるのでしょう）

import sys

n = int(input())

if n == 0:
    print(0)
    sys.exit()

m = (n - 1) // 2

a = [1]
b = [1]

for i in range(m):
    a1 = a[-1] + b[-1]
    b1 = a[-1] + 2 * b[-1]
    a.append(a1)
    b.append(b1)

s = sum(a) + sum(b)
print(s)

mayoidoro.rb

n = gets.to_i

if n == 0 then
    puts 0
    exit
end

m = (n - 1) / 2

a = [1]
b = [1]

m.times do |i|
    a1 = a.last + b.last
    b1 = a.last + 2 * b.last
    a.push(a1)
    b.push(b1)
end

s = a.inject(:+) + b.inject(:+)
puts s