Lesson 2: MaxCounters (Max Counters)

https://codility.com/programmers/lessons/2
Lesson 2:MaxCountersの解答がこちらになります。

これは結構面白い課題で、普通に問題の言う仕様でそのまま作ってしまうと、パフォーマンスが悪くて点数がもらえません。

たとえば、下のそういったかんじの実装ですと７７％しかもらえないのです。

 


--------------------------------------------
A Simple Solution
--------------------------------------------
struct Results solution(int N, int A[], int M) 

{
    struct Results result;

    result.C = calloc(sizeof(int), N);
    result.L = N;

    int max = 0;
    
    int i, j;
    for (i = 0; i < M; i++){
        int op = A[i];
        //if the op is max counter.
        if (op == N + 1){
            for (j = 0; j < N; j++){
                result.C[j] = max;
            }
        }
        //if the op is increase(x)
        else {
            //op is beweetn 1 to N, but the index for the array C 
            //is between 0 and (N-1). Decrease op to adjust it.
            op--; 
            result.C[op]++;
            if (result.C[op] > max){
                max = result.C[op];
            }
        }
    }

    return result;
}


おそらく、これはいちいちmax counter命令が発効された時に、配列を全部更新しているからで、それをやめれば良さそうです。

いちいち更新するかわりにフラグをおさめる配列を用意して、max counterの時はそれを一気に０クリアするだけ、そして、ある位置がincrease命令を発効されたら、その位置と対応するフラグをみて、初めてそこで更新という戦略にしてみました。

スコアは88%まであがりましたが、まだまだ先がありそうです。

--------------------------------------------
A Better Solution (1)
--------------------------------------------

struct Results solution(int N, int A[], int M) 

{

    struct Results result;

    result.C = calloc(sizeof(int), N);

    result.L = N;

    int* flg = alloca(sizeof(int) * N);

    memset(flg, 0x00, sizeof(int) * N);

    

    int max = 0;

    int maxAtTheLastMaxCntOp = 0;

    

    int i;

    for (i = 0; i < M; i++){

        int op = A[i];

        //if the op is max counter.

        if (op == N + 1){

            maxAtTheLastMaxCntOp = max;

            memset(flg, 0x00, sizeof(int) * N);    

        }

        //if the op is increase(x)

        else {

            //op is beweetn 1 to N, but the index for the array C 

            //is between 0 and (N-1). Decrease op to adjust it.

            op--; 

            if (flg[op] == 1){

                result.C[op]++;

            }

            else {

                result.C[op] = maxAtTheLastMaxCntOp + 1;

                flg[op] = 1;                

            }

            

            if (result.C[op] > max){

                max = result.C[op];

            }

        }

    }

    

    //apply the 'max counter' operation

    //to the slot(s) where it should be applied. 

    int j;  

    for (j = 0; j < N; j++){

        if (flg[j] == 0){

            result.C[j] = maxAtTheLastMaxCntOp;

        }

    }

    return result;

}

結局、フラグを使うのではダメだという事がわかりました。ここで気づくのは、もし、更新しようとしている位置が、過去のmax counterが発行された時の値より小さいかどうかだけ調べればフラグっていらないんですよね。そうするとフラグのクリアなどをする必要がなくなります。

この方針だと１００％になりますね。ちょっとした発想の転換を試される問題でした。

--------------------------------------------
A Better Solution (2)
--------------------------------------------
struct Results solution(int N, int A[], int M) 
{
    struct Results result;

    result.C = calloc(sizeof(int), N);
    result.L = N;
    
    int max = 0;
    int maxAtTheLastMaxCntOp = 0;
    
    int i;
    for (i = 0; i < M; i++){
        int op = A[i];
        //if the op is max counter.
        if (op == N + 1){
            maxAtTheLastMaxCntOp = max;
        }
        //if the op is increase(x)
        else {
            //op is beweetn 1 to N, but the index for the array C 
            //is between 0 and (N-1). Decrease op to adjust it.
            op--; 
            if (result.C[op] < maxAtTheLastMaxCntOp){
                result.C[op] = maxAtTheLastMaxCntOp + 1;
            }
            else {
                result.C[op]++;
            }     
            //update the max value if necessary.
            if (max < result.C[op]){
                max = result.C[op];
            }
        }
    }
    
    //apply the 'max counter' operation
    //to the slot(s) where it should be applied. 
    int j;  
    for (j = 0; j < N; j++){
        if (result.C[j] < maxAtTheLastMaxCntOp){
            result.C[j] = maxAtTheLastMaxCntOp;
        }
    }
    return result;
}