Lesson 13: CountTriangles (Count Triangles)

Lesson 13: CountTriangles

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

まず、配列をソートします。

この配列から三角形を探して行くのですが、ソートしたのでA[P] + A[Q] > A[R]だけをチェックすればいいことになります。なぜならつねに A[P] <= A[Q] <= A[R]となるので、 A[P] < A[Q] + A[R] と A[R] + A[P] > A[Q] はつねになりたちますね。

まずPの位置を決め、その次に隣にQ、その隣にRの状態にします。A[P] + A[Q] > A[R]  が成り立つあいだはRを右にスライドさせます。１回スライドするたびに(R - Q) 個の新しいコンビネーションが見つかることになりますね。Rの位置を固定して、Qの位置だけ変わるとすると(R-Q)個のQとRの組み合わせがみつかるということになるからですね。　 

もしRがこれ以上スライドできなくなった場合（上の条件が成り立たない場合）、こんどはQを一個動かしてみます。Qが大きくなったのでRが動かせるかもしれないからですね。もしQ==Rになった場合は、Rが重ならないように右にさらに一つ動かされます。

これを全てのかのうなPの位置に対して繰り返せばいいわけですね。

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

int compare_int(const void *a, const void *b)
{
   //don't do 'return *(int*)a - *(int*)b;',
   //as this can cause underflow or overflow.

   if (*(int*)a == *(int*)b){
       return 0;
   }

   if (*(int*)a < *(int*)b){
       return -1;
   }
   
   return 1;
}

int solution(int A[], int N) 
{
    qsort(A, N, sizeof(int), compare_int);

    int cnt = 0;
    
    int p, q, r, ap, aq, ar;

    p = 0;
        
    for (   ; p <= N - 3; p++){
        ap = A[p];
        
        q = p + 1;
        r = p + 2;

        while (r < N){
            aq = A[q];
            ar = A[r];
            
            if (ap + aq > ar){
                cnt += r - q;
                r++;
            }
            else {
                q++;
                if (r == q){
                    r++;
                }
            }
        }

    }
    
    return cnt;
}