私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「マヨイドーロ」（CodeIQ）を参照してください。
次のようにな経路があります。
X
\
Y - A - B - C -Z
Xから入って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から初めても同じで、右に進むパターンと左に進むパターンを再帰で処理すれば全パターン列挙できます。
プログラムの本体です。
引数に前回の位置、何回反転したか、進行方向、経路のログをもらって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以上の最小偶数）になるということです。
解説を読んだ感想は「さすがに自分の数学能力でこれは解けない」でした。