CodeIQ:マヨイドーロ

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「マヨイドーロ」(CodeIQ)を参照してください。

問題の概要

次のようにな経路があります。

      X
       \
Y - A - B - C -Z
Xから入ってYに出るのですが、標準入力から「反転回数」が与えられます。
A、B、Cの地点で反転できます。
入力された反転回数以下の反転でYにでられるルートのパターンはいくつあるでしょうか。

私のプログラム

Javaで解答しています。
ごく素朴にシミュレートするプログラムで正しくシミュレートします。
しかし、入力値が大きくなると(実際には50の場合で)時間切でダメになりました。
最初に挑戦した問題で、挑戦した問題のうち2016.1.9現在で正解できなかった唯一の問題です。

import java.io.*;

public class Main {

private char[] Route = {'Y', 'A', 'B', 'C', 'Z'};
private int N = 0;
private int P = 0;

public Main(int n){
    N = n;
}

// pos:前回の場所の要素番号
// count:反転回数
// direction: +1=Z方向に進んでいる、-1=Y方向に進んでいる
// route: 経路印字用文字列
private void toNext(int pos, int count, int direction, String route){
    // 反転回数が上限を超えたら終わり
    route += Route[pos];

    if(count > N){
        route += "[OVER]";
        return;
    }

    if(Route[pos] == 'Y'){
        P++;
        return;
    }
    else if(Route[pos] == 'Z'){
        return;
    }

    toNext(pos + direction, count, direction, route);
    toNext(pos - direction, count+1, -1 * direction, route);
}

private void printPatternCount(){
    System.out.println(P);
}

public static void main(String[] args) throws IOException {
	BufferedReader stdReader =	new BufferedReader(new InputStreamReader(System.in));
	String line;
	while ((line = stdReader.readLine()) != null) {
		int n = 0;
		try{
			n = Integer.valueOf(line);
			Main mr = new Main(n);
			mr.toNext(2, 0, +1, "");
			mr.printPatternCount();
		}
		catch(Exception e){
			continue;
		}
	}
	stdReader.close();
}

}

解説

正解できませんでしたが、自分のプログラムを解説します。

基本的な考え方

全パターンをシミュレーションするのは再帰を使えば容易です。問題文はXからスタートですが実際にはAから初めても同じで、右に進むパターンと左に進むパターンを再帰で処理すれば全パターン列挙できます。

toNext()

プログラムの本体です。
引数に前回の位置、何回反転したか、進行方向、経路のログをもらって1回分進むと言うプログラムです。
1回進むごとに反転回数をチェックし、上限に達するかYかZに達したら終了、そうでなければもう1回を繰り返すわけです。経路はログに残してあってログの要素数で反転回数がわかります(デバッグのためカウントではなくログにしました)。

このプログラムは素朴にシミュレーションしているだけなので正しい結果を導けますが時間がかかります。入力値が小さければ私のプログラムでも問題ありません。が、あっという間に組み合わせがとんでもない数になります。50だとざっと2^50パターンになってしまいます。
シミュレーションではダメで漸化式を求めないと正解できないことは明らかでしたが、私には漸化式を求めることができずギブアップしました。

解説を読んで

問題が締め切られて公開された解説を要約すると、漸化式を求めてそれを解いた場合、入力値以下の最大の奇数をNとした場合、「フィボナッチ数列 Fn の「添字が 3 以上の奇数で、かつ添字が N + 2 以下」である項を加 えた数」、さらにF2k = Fk-1 + ・・・ + F3 + F1なので、パターンPはP=FS-1(SはN+2以上の最小偶数)になるということです。

解説を読んだ感想は「さすがに自分の数学能力でこれは解けない」でした。

雑感

この後しばらく別の問題をやったりしていて知ったのですが「競技プログラミング」という分野があって、そのあたりではフィボナッチ数列は割と一般的な知識みたいです。
この問題は「当該領域で一通りの経験があれば可能」レベルでしたが「当該領域」は「競技プログラミング」を指すのでしょうか? 一般的なシステム開発ではこれほどの数学は要求されないと思うのですが。

(2016.5.10 追記)
この問題を今やったらできるか考えてみました。
結果としては「できる」です。
手順は次のようになります。
  1. シミュレーションは書けているので数列の先頭部分10個くらいは求められます。「2,2,7,7,20,20,54,54,143,143,376,376」となります。
  2. どうも奇数番と偶数番は同じ値になるようですので「2,7,20,54,143,376」をOEISで調べます。
  3. 「A035508 a(n) = Fibonacci(2n+2) - 1.」がヒットします。
  4. この結果から、フィボナッチ数列の一部であることがわかるのでフィボナッチ数列を調べてプログラムを書くことができます。
この問題は初めて挑戦したプログラムの問題で、前述の通り「数学の知識がないとこんなものわからないだろう」と思いましたが、現状ではよくやる手で解けます。多分、簡単とは思わないでしょうが無茶苦茶難しいとも思わないでしょう。つまるところ、問題をいくつも解いている間に私が成長したということだと思います。