Lesson 5: Fish (Fish)

Lesson 5: Fish
https://codility.com/programmers/lessons/5

シンプルな解答はスタックを使うことにより実現できます。
まず、下って行く魚だけにスタックを用意しましょう。

そして、魚のサイズと向きの配列を先頭からスキャンして行きましょう。

もし現在見ているポジションの魚が下っているなら、そのままスタックにのせます。

もし現在見ているポジションの魚が登っているなら、このスタックから、自分より大きな魚に出会うまで魚を食べ続けます。自分より大きな魚にであったら、その場で死んでしまいますが、あわずにスタックが空になった場合、それは上流の端までたどり着いたということなので、生き残ります。

最終的には、上流に向かって生き残った魚の数と、最後にスタックに残った下流に進んで行った魚の数が、全体的に生き残った魚の数の合計となります。

これで１００％のスコアがもらえます。

#include <alloca.h>

int solution(int A[], int B[], int N) 
{
    int memsize = sizeof(int) * N;

    //stack (memory & index)
    int* down   = (int*)alloca(memsize);
    
    int d = 0;

    //the counter for the fish that reached to the end of the river.    
    int cnt_reached = 0;

    int i;
    for (i = 0; i < N; i++){        
        
        //if the fish is going upstream,
        //check if it can reach the upper end.
        if (B[i] == 0){
            while(1){
                //if there is no more fish against it,
                //it reaches the upper end.
                if (d == 0){
                    cnt_reached++;
                    break;
                }
                //met a bigger one, they it is eaten..
                if (down[d - 1] > A[i]){
                    break;
                }
                //we keep on eating the fish...
                d--;
            }
            continue;
        }
        down[d] = A[i];
        d++;
    }
    
    return cnt_reached + d;
}