Lesson 8: Peaks (Peaks)

Lesson 8: Peaks
https://codility.com/programmers/lessons/8

まず、配列Aのなかからpeekを探し、別の配列の中にその見つけたpeekのインデックスをストアして行きます。

もし、peekがなければ、0を返して良いですね。 


ですから、もし、一つでもpeekがあれば、とりあえずから、peek_cntから一つずつ1に向かってカウンタを減らしつつ、それがNの約数であれば、現在の値で各ブロックに最低１つのpeekが含まれていることという条件が満たせるか調べて行きます。失敗したら次の約数に、成功したらその時点で答えが得られますね。

(なぜpeek_cntからスタートするかというと、かならずどのブロックにもpeekが入って行なければならないということは、それが最大分割数になりますね）

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

#include <alloca.h>

int solution(int A[], int N) 
{
    //we need at least 3 elements to have a peek.
    if (N < 3){
        return 0;
    }

    //we will never have the number of peeks larger than N / 2.
    int *peeks = (int*)alloca(sizeof(int) * (N / 2));
    int peek_cnt = 0;
    
    //find peeks
    int i;
    for (i = 1; i < N - 1; i++){
        if (A[i - 1] < A[i] && A[i] > A[i + 1]){
            peeks[peek_cnt++] = i;
        }
    }
    
    //if there is no peek, return 0
    if (peek_cnt == 0){
        return 0;
    }
    
    //let's check from the block of the possible maxim number of blocks.

    //as we have at least one peek, we can say the minimum number of blocks 
    //that meets the given condition is 1.
    int maxdiv = 1; 
    for (i = peek_cnt; i > 0; i--){
        if (N % i != 0){
            continue;
        }
        
        //let's check if this number satisfies the conditon.
        int elems_for_each_block    = N / i;
        int next_block_end          = elems_for_each_block;

        int pidx = 0; //the index of the peek to check 
        int flg  = 1; //assume the number satisfies the condition first.

        while(1){
            //check if this block contains any peek.
            if (pidx >= peek_cnt || next_block_end <= peeks[pidx]){
                //no peeks detected, this is not a right choice.
                flg = 0;
                break;
            }
            
            //skip the peeks within the current block.
            while(pidx < peek_cnt && peeks[pidx] < next_block_end){
                pidx++;
            }

            next_block_end += elems_for_each_block;
            if (next_block_end > N){
                break;
            }
        }
        
        //at least one peek is contained in every block.
        if (flg){
            maxdiv = i;
            break;
        }  
    }
    
    
    return maxdiv;
}

ググったところ、prefix sumの考え方を利用して、効率的なコードを書いている人たちが居ました。peekのインデックスを保持する代わりに、元配列Aの該当インデックスまでに見つかったpeekの総数を別の配列に保持しています。

これをすると、あるブロックのサイズが与えられた条件を満たすかどうかを、シンプルかつ効率的に行えるようになります。

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

#include <alloca.h>

int solution(int A[], int N)
{
    //for N < 3, there is no peek.
    if (N < 3){
        return 0;
    }

    //make the prefix sum of the number of the peeks at the index.
    int* peek_cnt_prefix_sum = (int*)alloca(sizeof(int) * N);
    
    peek_cnt_prefix_sum[0] = 0;
    int i;
    for (i = 1; i < N - 1; i++){
        peek_cnt_prefix_sum[i] = peek_cnt_prefix_sum[i - 1];
        if (A[i - 1] < A[i] && A[i] > A[i + 1]){
            peek_cnt_prefix_sum[i]++;
        }
    }
    
    peek_cnt_prefix_sum[N - 1] = peek_cnt_prefix_sum[N - 2];

    //no peek found.
    if (peek_cnt_prefix_sum[N - 1]  == 0){
        return 0;
    }
    
    int maxdiv = 1;
    for (i = peek_cnt; i > 0; i--){
        if (N % i != 0){
            continue;
        }
        
        int elems_for_each_block = N / i;
        
        //keep on checking
        int flg = 1; //assume this divisor of N satisfies the condition.

        int next_block_end = elems_for_each_block - 1;
        int current = peek_cnt_prefix_sum[0];
        while(next_block_end < N){  
            
            int next = peek_cnt_prefix_sum[next_block_end];
            //no peeks found between current and next.
            if (current >= next){
                flg = 0;
                break;
            }
            current = next;
            next_block_end += elems_for_each_block;
        }
        
        //if this divisor of N satisfied the condition,
        //it is the answer.
        if (flg){
            maxdiv = i;
            break;
        }
    }
    
    return maxdiv;
}