Lesson 11: Ladder (Ladder)

Lesson 11: Ladder
https://codility.com/programmers/lessons/11

この問題は実際はフィボナッチ数の計算の問題です。
とりあえず、０段のはしごを登るパターンから一つ一つ増やして考えて行きましょう。

段数 : 登るパターンの数
０　段 : 0 

１　段 : 1 --> 0

２　段 : 2 --> 1 --> 0
            |-> 0

３　段 : 3 --> 2--> 1 --> 0
            |   |-> 0
            |
            --> 1 --> 0

上のようにi段のはしごを上る時のパターンの数は、i-1段のはしごを上る時のパターンの数と、i-2段のはしごを上る時のパターンの数の合計になりますね。（例えば、こう考えてみてください。もし、最初に１段あがったら、そこからのパターン数はi-1段のパターン数と同じですね。同様に、もし最初に２段あがったら、そこからのパターン数はi-2段のはしごのパターン数と同じですね。だからこの二つのパターン数を単に足せば良いわけです。）

もしO(L)のメモリ量を使ってよいならば、Lesson 11で勉強したO(L)の各iの値を記憶しつつつフィボナッチ数を求めるアルゴリズムを使えますね。

ただし、あんまり大きいLですと、確実にCではオーバーフローしますね。ですが、問題のほうでは、実際のパターン数を返さないで良いようになっています。実際には2^B[i]で割った場合の余りを返せばよく、Bの最大値は３０になっています。ですので、Codilityの環境ではC言語のintは３２ビットなのですから、単純に上位２ビットを削ればいいですね。充分範囲内となっています。

このためにフィボナッチ数を計算するとkにビット演算の&を使って上位２ビットを常に０にするようにしましょう。上位２ビットはこの問題の求める答えに関係ないですからね。

また、実際の結果を返す時に、2^B[i] でさらに余りを取るのを忘れないようにしましょう。

これで100%のスコアがもらえます。

#include <alloca.h>

struct Results solution(int A[], int B[], int L) 
{
    //the problem states that B <= 30, which means
    //we only have to consider the_number_of_combination % 2^30. 
    //and the combnation increases like the fibonacci numbers.
    int* fibM = (int*)alloca(sizeof(int) * (L + 1));
    
    fibM[0] = 0;
    fibM[1] = 1;
    fibM[2] = 2;
    
    int i;
    for (i = 3; i <= L; i++){
        //0x 3FFF FFFF = 0B 0011 1111 1111 1111 1111 1111 1111 1111.
        //we cut off the 2 bits from MSB to avoid overflow by applying bitwise-and.
        fibM[i] = (fibM[i - 1] + fibM[i -2]) & 0x3FFFFFFF;
    }

    struct Results result;

    result.C = (int*)malloc(sizeof(int) * L);
    result.L = L;
    
    for (i = 0;  i < L; i++){
        //it may be better to use fibM[A[i]] & ((1 << B[i]) - 1);
        result.C[i] = fibM[A[i]] % (1 << B[i]);
    }
    
    return result;
}