Lesson 13: CountDistinctSlices (Count Distinct Slices)

Lesson 13: CountDistinctSlices
https://codility.com/programmers/lessons/13

範囲を右に拡大するたびに、拡大前にあった長さのスライスは全てもう一回右にうごかせる＝スライスが増えることになります。また、範囲が広がったことにより、その長さのスライスも追加できますね。

ということはで、一つ範囲を広げるごとに、現在の長さ分のスライスが増えるということになります。

下記のリンクの人の実装が非常によかったので、そのままCにうつしました。

https://github.com/acprimer/Codility/blob/master/src/Lesson13/CountDistinctSlices.java

これで１００％のスコアです

#include <alloca.h> #include <memory.h> int solution(int M, int A[], int N) {      int memsize = sizeof(int) * (M + 1);      int*found = (int*)alloca(memsize);      memset(found, 0xFF, memsize);      
    int r = 0;      int l = -1;      
    int cnt = 0;

    for ( ; r < N; r++){    
        if (found[A[r]] > l){ 
            l = found[A[r]];
        }

        cnt += r - l;
        
        found[A[r]] = r;
        if (cnt > 1000000000){
            return 1000000000;
        }
    }      
    return cnt; }




他の解法も実は頑張ってやっていたのですが、オーバーフローのバグで間違った答えがでて、気づかず四苦八苦していました。こういったコーディングの問題は、面接とかでは迷わずbig integerのある言語を使うべきですね。

下のコードではまず、既にマークした数字にであったら、とりあえずその範囲までに可能なdistinct sliceの数を全て計算し、その後、次のラウンドに再度出て来てしまうスライスの数を計算して、それを引いています。二重にカウントすると答えが間違ったものになってしまいますからね。

このコードはlとrの幅に依拠しているので、そこで余りに大きい数で計算することになると、オーバーフローしてしまうためlong longで計算しています。

このコードも100%のスコアが得られます。

#include <alloca.h> #include <memory.h> int solution(int M, int A[], int N) {      int memsize = sizeof(int) * (M + 1);      int* found = (int*)alloca(memsize);      //this initialize the array with -1.      memset(found, 0xFF, memsize);      
    int r = 0;      int l = 0;      
    int cnt = 0;      
    for ( ; r < N; r++){          if (found[A[r]] == -1){
            found[A[r]] = r;
            continue;
        }
     
        //to avoid overflow, we use long long here...
        long long all = ((long long)r - l) * (r - l + 1) / 2;
        long long tmp = (long long)r - (found[A[r]] + 1);
        long long sub = tmp * (tmp + 1) / 2;
         
        //to avoid overflow...
        if (all - sub >= 1000000000){
            return 1000000000;
        }
        
        cnt += all - sub;
        if (cnt >= 1000000000){
            return 1000000000;
        }
        while (l <= found[A[r]]){
            found[A[l]] = -1;
            l++;
        }
        found[A[r]] = r;
    }      
    //to avoid overflow      long long rest = ((long long)r - l) * (r - l + 1) / 2;      if (rest > 1000000000){          return 1000000000; 
    }      
    cnt += rest;      
    return cnt > 1000000000 ? 1000000000 : cnt; }




上のコードは実はさらに簡単にできます。最初のコードと同じようにlの位置でそれまでにみつかったかどうか判定すれば、フラグをいちいちクリアする必要はないですね。

これで１００％のスコアになります。

#include <alloca.h> #include <memory.h> int solution(int M, int A[], int N) { int memsize = sizeof(int) * (M + 1); int* found = (int*)alloca(memsize); //this initialize the array with -1. memset(found, 0xFF, memsize); int r = 0; int l = 0; int cnt = 0; for ( ; r < N; r++){ if (found[A[r]] < l){ found[A[r]] = r; continue; } //to avoid overflow, we use long long here... long long all = ((long long)r - l) * (r - l + 1) / 2; long long tmp = (long long)r - (found[A[r]] + 1); long long sub = tmp * (tmp + 1) / 2; //to avoid overflow... if (all - sub >= 1000000000){ return 1000000000; } cnt += all - sub; if (cnt >= 1000000000){ return 1000000000; } l = found[A[r]] + 1; found[A[r]] = r; } //to avoid overflow long long rest = ((long long)r - l) * (r - l + 1) / 2; if (rest > 1000000000){ return 1000000000; } cnt += rest; return cnt > 1000000000 ? 1000000000 : cnt; }