マヨイドーロ問題の解答コード

マヨイドーロ問題

結城浩さんがCodeIQで久しぶりに出題したので解いてみた。

締め切りも過ぎたので、私の解答ロジック&コードを公開してみます。

ロジック

最後は必ず左向きになる&スタートが右向きなので、 Nが奇数の時の結果と (N+1) の結果は同一。なのでNは奇数しか考えない。

AまたはCで折り返した時はその後の折り返しパターンは2種類。 Bで折り返した時はそのその後の折り返しパターンは1種類

ゴールは折り返し残り0回でAに来たタイミングとみなせるので、

折り返し1 : A に向かうパターン[B,C]x1 の2パターン
折り返し2 : C に向かうパターン[A,B]x1  + B に向かうパターン[A]x1 の3パターン
折り返し3 : A に向かうパターン[B,C]x2  + B に向かうパターン[C]x1 の5パターン
折り返し4 : C に向かうパターン[A,B]x3  + B に向かうパターン[A]x2 の8パターン
折り返し5 : A に向かうパターン[B,C]x5  + B に向かうパターン[C]x3 の13パターン
折り返し6 : C に向かうパターン[A,B]x8  + B に向かうパターン[A]x5 の21パターン
折り返し7 : A に向かうパターン[B,C]x13 + B に向かうパターン[C]x8 の34パターン

として、折り返す数が奇数の時のパターン数を合計すると結果になる。

1 : 2
3 : 2 + 5 = 7
5 : 2 + 5 + 13 = 20
7 : 2 + 5 + 13 + 34 = 54

で、各折り返し回数でのパターン数を見てみると… (1, 1,) 2, 3, 5, 8, 13, 21, 34… これはひょっとして…フィボナッチ数列？

しかも、最終的な結果として、Nが奇数の時のパターン数合計は「N+3番目のフィボナッチ数 - 1」の値であることがわかる。

つまりは、以下の式で結果が求まる。 P = fib(N + 3) - 1

解答コード ruby 編

最初Goで提出したら、入力値 1000 からuint64でもオーバーフローしてしまい失敗…。

ならrubyでやったれ。

#! ruby -Ku

# n個目のフィボナッチ数を取得（参考 : http://qiita.com/mathhun/items/4c117d33028a888f6fcf）
def fib(n)
	return n if n <= 1

	n0, n1 = 0, 1
	current = 0
	(n - 1).times do
		current = n0 + n1
		n0, n1 = n1, current
	end
	current
end

def get_mayoi_pattern_count(n)
	return 0 if n <= 0
	n -= 1 if (n % 2) == 0
	fib(n + 3) - 1
end

# 入出力
while line = gets
  n = line.chomp.to_i
  v = get_mayoi_pattern_count(n)
  puts "#{v}"
end

で無事正解100%。

解答コード Go 編

最初 ruby で正解した時に解説のPDFがあるのに気付かず、見逃してしまった…のだが、その後結城さんご本人より「もう一度解答投稿すれば見れますよ。」とのお言葉をいただく。

とゆー経緯で、前回オーバーフローして失敗した Go でやってみることにした。

Goでは、巨大な整数を扱うpackageとして ‘math/big’ が用意されているのだが、言語仕様として演算子のオーバーロードが出来ないため若干見辛くなっている。

が、昔はみんなこうだったよな…とか思いつつ無事完成。

コードは以下（提出時よりも若干整理しています）

package main

import (
	"bufio"
	"fmt"
	"math/big"
	"os"
	"strconv"
)

// フィボナッチ数を求める
func fib(n int) (current *big.Int) {
	current = big.NewInt(int64(n))
	if n <= 1 {
		return
	}

	n0 := big.NewInt(0)
	n1 := big.NewInt(1)
	for i := 0; i < n-1; i++ {
		current.Add(n0, n1)
		n0.Set(n1)
		n1.Set(current)
	}
	return
}

// マヨイドーロパターン総数算出
func getMayoiPatternCount(n int) (result *big.Int) {
	result = big.NewInt(0)
	if n <= 0 {
		return
	} else if (n % 2) == 0 {
		n--
	}

	result.Sub(fib(n+3), big.NewInt(1))
	return
}

func main() {
	io := bufio.NewReader(os.Stdin)
	for {
		line, _, err := io.ReadLine()
		if err != nil || len(line) <= 0 {
			break
		}

		n, _ := strconv.ParseInt(string(line), 10, 32)
		fmt.Println(getMayoiPatternCount(int(n)).String())
	}
}

big.Int 型の各種メソッドは全てポインタを返すようになっているので、 L22,L23 あたりの値の入れ替えの時に

n0,n1 = n1,current

とかすると正しく動かない。

ま、値を設定するときはちゃんと Set しなさい。ということですな。

感想

上記Goの解答で無事に解説PDFを読めたのだが、ロジック的にも大体同じような感じだったので、一安心。

もっと詰めれば、フィボナッチ数列を求めるところを最適化可能だと思うのだが、今回これで全ケース0秒と出たので良しとした。そこ手抜きとか言わない。

結城さんの問題は、単純にロジックを実装するだけでなく、もう一捻りすることで気持ちよく解答する事ができる問題が多いので面白いなーと思う。

ま、いつもそれほど気持ちよくないのは私の思慮が足りないからですがｗ

CodeIQのこの手の問題は時折解いているのだが、普段仕事ではあまりアルゴリズムを考えることも無いので、ちょうど頭の体操になって良い。

今後もまた何かあれば挑戦してみたいと思う。

spec-R

らが～の備忘録。

マヨイドーロ問題の解答コード