https://codility.com/programmers/lessons/11
これは難しい問題(ambitious)とされている問題ですね。ですからちょっとずつといきましょう。
まず、25番目と26番目のフィボナッチ数は75,025と121,393にそれぞれなります。Nが1から100,000の間と問題で定義されていますから25番目のフィボナッチ数までを計算すれば良いですね。
それから、再帰的にジャンプを繰り返して向こう岸（Nの位置）に届くかどうかを調べて行きます。成功したケースのうち、一番小さいものをとればいいですね。
この方法で実装したコードがしたになります。しかしながら、示されている通り、良いスコアはもらえませんね。タイムアウトさせられてしまうので、コードのcorrectnessもチェックを全部してもらえず、コードにバグがないかどうかも調べてもらえません。
#include <alloca.h>
void check(int* A, int pos, int* fibN, int fibN_length, int cnt, int* min, int N)
{
//we perform one more jump in this check
cnt++;
//try the largest jump as possible.
int fibIdx = fibN_length - 1;
int fib;
//check if the frog can arrive the other bank by the next jump.
while(fibIdx > 1){
fib = fibN[fibIdx];
//the forg reached to the other bank. this route is over.
if (pos + fib == N){
//update the min
*min = cnt < *min ? cnt : *min;
break;
}
else if (pos + fib < N){
break;
}
fibIdx--;
}
//now we seek for the smaller jumps can be used to investigate other routes.
while(fibIdx > 1){
fib = fibN[fibIdx];
//try recursion, if there is any leaf there.
if (A[pos + fib] == 1){
check(A, pos + fib, fibN, fibN_length, cnt, min, N);
}
fibIdx--;
}
return;
}
int solution(int A[], int N)
{
//for N = 0, 1, 2, the distance to jump from `-1' (the origin)
//can be 1, 2, 3. then we know these a fibonacci number.
if (N <= 2){
return 1;
}
//we now N <= 100,000. Since fib(25) == 75025, fib(26) = 121393,
//we only have to generate 25 fibonacci numbers.
int fibN_length = 26;
int* fibN = (int*)alloca(fibN_length * sizeof(int));
fibN[0] = 0;
fibN[1] = 1;
int i = 2;
while (i < fibN_length){
fibN[i] = fibN[i - 1] + fibN[i - 2];
//if one jump is enough, we can simply return here.
if (fibN[i] == N + 1){
return 1;
}
i++;
}
int min = 0x7FFFFFFF;
check(A, -1, fibN, fibN_length, 0, &min, N);
return min == 0x7FFFFFFF ? -1 : min;
}
ということは、パフォーマンスを改善する手段をみつけなければならないですね。問題は再帰的に全てのケースを調べてしまっていることです。次の実装では、いままで見つかった、向こう岸につける最小のジャンプ回数を記憶しておき、以後のケースではこの回数にたどり着いても向こう岸にたどり着いていなかったら、そこで再帰を打ち切るようにしてみます。
したにこの実装を示します。100%のcorrectnessのスコアはもらえましたが、パフォーマンスは83%ですね。合計で91%のスコアになっています。やはりまだパフォーマンスを上げる方法が必要です。
#include <alloca.h>
void check(int* A, int pos, int* fibN, int fibN_length, int cnt, int* min, int N)
{
//we perform one more jump in this check
cnt++;
//we will have one more jump later in this code.
//so if cnt is already min, we don't have any smaller number
//of jumps in this route.
if (cnt >= *min){
return;
}
//try the largest jump as possible.
int fibIdx = fibN_length - 1;
int fib;
//check if the frog can arrive the other bank by the next jump.
while(fibIdx > 1){
fib = fibN[fibIdx];
//the forg reached to the other bank. this route is over.
if (pos + fib == N){
//update the min. As we checked cnt < *min already,
//cnt is always smaller than *min here.
*min = cnt;
break;
}
else if (pos + fib < N){
break;
}
fibIdx--;
}
//now we seek for the smaller jumps can be used to investigate other routes.
while(fibIdx > 1){
fib = fibN[fibIdx];
//try recursion, if there is any leaf there.
if (A[pos + fib] == 1){
check(A, pos + fib, fibN, fibN_length, cnt, min, N);
}
fibIdx--;
}
return;
}
int solution(int A[], int N)
{
//for N = 0, 1, 2, the distance to jump from `-1' (the origin)
//can be 1, 2, 3. then we know these a fibonacci number.
if (N <= 2){
return 1;
}
//we now N <= 100,000. Since fib(25) == 75025, fib(26) = 121393,
//we only have to generate 25 fibonacci numbers.
int fibN_length = 26;
int* fibN = (int*)alloca(fibN_length * sizeof(int));
fibN[0] = 0;
fibN[1] = 1;
int i = 2;
while (i < fibN_length){
fibN[i] = fibN[i - 1] + fibN[i - 2];
//if one jump is enough, we can simply return here.
if (fibN[i] == N + 1){
return 1;
}
i++;
}
int min = 0x7FFFFFFF;
check(A, -1, fibN, fibN_length, 0, &min, N);
return min == 0x7FFFFFFF ? -1 : min;
}
ここで、方針をがらっと変えてみましょう。
まず、有る場所から次のジャンプで向こう岸（Nの位置）にたどり着け、その場所に来るまでに２つの別のルートがあると考えてみましょう。それぞれのルートで必要なジャンプの数が２と３とします。となるとこれらのルートを通った上で次のジャンプで向こう岸にたどり着けるのですから、それぞれのルートを通ってここまで着た場合の後の最小のジャンプ回数はそれぞれ、３、４となりますよね。
ところが、答えとしてほしいのは「最初のジャンプ回数」だけなので、４の答えのほうはかんけいないですよね。つまり、ある位置にくるまでにかかった、最小のジャンプの回数だけを覚えておけばいいのです。
配列reachedを用意し、それぞれの位置にくるまでに必要だった最小のジャンプの数を対応する各々の位置に記憶することにしましょう。reached[i]にはiの位置にくるために必要な最小のジャンプ回数が記録されている訳ですから、次のジャンプはreached[i] + 1回目のジャンプであると考えてしまえばいいのです。
まず、最初のジャンプでいけるところをすべて調べます（つまり、スタート位置からフィボナッチ数の距離にあり、そこにleafがあること場所です）。そこに１回のジャンプでいけるとメモします。
それから、配列reachedを頭からスキャンして行き、最初のジャンプでたどり着けたところを見つけて行きましょう。もし見つかったら、そこか次のジャンプでたどり着けるところ全てに「２回目のジャンプでたどり着けた」ことをreachedの該当位置に記憶します。こういったことを最初から最後までやれば、各位置にくるための最初のジャンプ数がわかりますよね。
これを繰り返して向こう岸にたどり着いた時の最小回数も調べておけば良さそうです。
これで１００％のスコアがもらえました。
#include <alloca.h>
#include <memory.h>
int solution(int A[], int N)
{
//for N = 0, 1, 2, the distance to jump from `-1' (the origin)
//can be 1, 2, 3. then we know these a fibonacci number.
if (N <= 2){
return 1;
}
//each reached[i] cell remembers the minimum jumps made to reach there so far.
int reached_size = sizeof(int) * N;
int* reached = (int*)alloca(reached_size);
memset(reached, 0x00, reached_size);
//these two cells can be reached when there are leaves there.
//since 0 and 1 can be reached by the first jump, we only care if
//there is a leaf or not.
reached[0] = A[0];
reached[1] = A[1];
//we now N <= 100,000. Since fib(25) == 75025, fib(26) = 121393,
//we only have to generate 25 fibonacci numbers.
int fibN_length = 26;
int* fibN = (int*)alloca(fibN_length * sizeof(int));
fibN[0] = 0;
fibN[1] = 1;
int i = 2;
while (i < fibN_length){
fibN[i] = fibN[i - 1] + fibN[i - 2];
//if one jump is enough, we can simply return here.
if (fibN[i] - 1 == N){
return 1;
}
//we also mark the position that can be reached by the first jump.
if (fibN[i] - 1 < N && A[fibN[i] - 1] == 1){
reached[fibN[i] - 1] = 1;
}
i++;
}
//let's check each cell
int min = 0x7FFFFFFF;
for (i = 0; i < N; i++){
//if the cell is not reachable, we can neglect it.
if (reached[i] == 0){
continue;
}
int min_jumps_to_here = reached[i];
int j;
for (j = 2; j < fibN_length; j++){
int next_pos = i + fibN[j];
//if we can reach the other bank (the position N),
// update min if necessary.
if (next_pos == N){
min = min_jumps_to_here + 1 < min ? min_jumps_to_here + 1 : min;
break;
}
//if the next jump is too large, or there is no leaf there,
//we can neglect this jump.
if (next_pos > N || A[next_pos] == 0){
continue;
}
//if we have never reached to the next position before, or we can reach
//the next position with less jumps, update the min number of jumps
// at the position.
if (reached[next_pos] == 0 ||
reached[next_pos] > min_jumps_to_here + 1){
reached[next_pos] = min_jumps_to_here + 1;
}
}
}
return min == 0x7FFFFFFF ? -1 : min;
}
0 件のコメント:
コメントを投稿