私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「今週のお題：寝過ごしても大丈夫？」（CodeIQ）を参照してください。
問題を引用します。
（前略）
電車で出発駅から目的の駅まで移動してみます。
乗るときは目的の駅に向けて、方向を間違えずに乗りますが、居眠りして乗り過ごしてしまう可能性があります。
一度折り返した駅や出発駅で再度起きることはなく、また目的の駅までに降りることはないものとして、目的の駅までの移動パターンを考えます。
例えば、5つの駅がある路線で、乗車駅と降車駅が図のように2番目と3番目のとき、降車駅までの移動パターンは図の7通りが考えられます。1 ┌┐ ┌┐ ┌┐ ┌┐ 2 o o o o|| o|| o|| o|| 3 ↓ |↑ |↑ ||↓ |||↑ ||↓ |||↑ 4 └┘ || └┘ └┘|| || ||└┘ 5 └┘ └┘ └┘ └┘【問題】
標準入力から駅の数nと、乗車駅と降車駅の番号が順にコンマ区切りで与えられるとき、目的の駅までの移動パターンが何通りあるかを求めてください。(駅の番号は1～nまでを順に付与するものとし、駅の数nは最大で15とします。）
C言語で解答しています。
#include <stdio.h>
unsigned long long Cnt;
unsigned int VISIT[15] = {
0x00000001, 0x00000002, 0x00000004, 0x00000008,
0x00000010, 0x00000020, 0x00000040, 0x00000080,
0x00000100, 0x00000200, 0x00000400, 0x00000800,
0x00001000, 0x00002000, 0x00004000,
};
void createRoute(int now, int ed, int visited, int dirct, int stations){
int i=0;
visited |= VISIT[now];
if(now == ed){
Cnt+=1;
return;
}
if(dirct < 0){
for(i=0; i<=ed; i++){
if(visited & VISIT[i]){
continue;
}
createRoute(i, ed, visited, -1*dirct, stations);
}
return;
}
else{
for(i=stations-1; i>=ed; i--){
if(visited & VISIT[i]){
continue;
}
createRoute(i, ed, visited, -1*dirct, stations);
}
return;
}
}
int main(int argc, char* argv[]){
char str[16] = {0};
while( fgets(str, sizeof(str), stdin) != NULL ){
int st = 0; // 開始
int ed = 0; // 終了
int stations = 0; // 駅数
int visited = 0; // 到達駅
sscanf(str, "%d,%d,%d", &stations, &st, &ed);
createRoute(st-1, ed-1, visited, ed-st, stations);
printf("%llu\n", Cnt);
}
}
最初Pythonで回答しましたが、駅数15で出発7、終了8のパターンで制限時間内に処理が終了せずリジェクトされたためCでやり直しました。なのでこのプログラムは再提出版です。
単純にシミュレートして全パターンを数え上げています。
この問題の場合、折り返す駅はゴールの駅の反対側にしかないので単純な順列よりもパターンが少なくなります。問題の性質上、いかにも時間切れで失敗しそうですが、試しにやってみたら結構早かったのでシミュレーションでチャレンジしてみました。
結果、Pythonではダメだったわけですが。
Pythonを覚えて以来、コードを書きやすいのでPythonをメインに使うようになりましたが、CやC++は実行速度が圧倒的に早いという利点があります。どのくらい早いかというと私のローカル環境で素数を数えるプログラムを実行した場合、約17.5倍の性能差がありました。
この問題のPythonのプログラムで駅数15で出発7、終了8のパターンを実行するのにかかった時間は19秒余りでした。真面目に考えるなら問題を数学的に問題を解いて計算だけで結果を求めるべきでしょうが、CかC++で書き直して少し工夫すれば1秒を切れそうだったのでシミュレーションで押し切ることにしました。
もとのPythonのプログラムも基本的な作りは上記のプログラムと同じです。違う部分といえばvisitedに渡されるのが未到達の駅のリストでした。そのままやるのであればstd::listが使えるC++になります。
しかし、std::listを使ってPythonのプログラムのまま移植すると19/17.5=1.08（秒）なので少し性能が足りていません。なのでこの部分に工夫を加えてCでやることにしました。
この関数が処理の本体です。
引数の意味は次の通りです。
処理としては単純で、次のような流れになっています。
ここで工夫しているのがvisitedの扱いです。
何も考えずPythonのプログラムを移植するなら要素数15の配列（最大駅数が15だから）を作ってそれで管理するのですが、再帰呼び出しされるたびにコピーしなければなりません。これは相当なオーバヘッドになることは明らかです。
なのでビットフラグを使うことにしました。駅に到達するごとにvisitedのビット位置を1にします（13行目）。1を立てる場所はnowの値からビットシフトして決めることもできますが、このくらいの数なら表にしてしまうのが簡単でわかり易いと思います（4〜9行目）。ちなみに宣言時に配列様子数を入れているのはミスです。unsigned int VISIT[] = {…}と宣言すべきでした。
この方法なら到達済み駅のリストをコピーしなくて良いですし、22行目や31行目のような判定もリストを検索することなくたった一回の計算できるので高速です。実際、上記のプログラムで駅数15で出発7、終了8のパターンを実行すると0.45秒くらいになりました。単純にCに移植したら1.08秒くらいだったとするとこの工夫で2.4倍程度の高速化ができたということになります。
この問題は多分出題者の想定する模範解答ではありません。同じ処理をスクリプト言語でやると時間切れは確実でしょうしJavaでも微妙な感じだと思います。
ちなみに、私はビットフラグを使うのは結構好きです。しかし、以前の会社にいた時一緒に仕事をした外注の方（かなり優秀な人だった）がビットフラグの手法を知らなくて驚いたことがあります。でも、JavascriptとかPHP、PerlのようなLLでは見かけない気がするのでそれまでの仕事によっては一般的ではない手法なのかもしれません。