Lesson 4: Triangle (Triangle)

これも算数の問題ですね。

まず、配列を昇順にソートしましょう。
すると、かならず0 <= P < Q < R < Nにたいしては、A[P] <= A[Q] <= A[R]となりますね。

とりあえず、全部正の整数０以上の整数と考えましょう。
(0 <  A[P] <=  A[Q] <= A[R]).

ソートされているので、以下の事が言えます。

条件 'A[P] < A[Q] + A[R]' は常に成り立つ。
条件 'A[Q] < A[P] + A[R]' も常に成り立つ。
（A[R]は既に、A[P]、A[Q]よりも大きいですから、正の数を足しても大きいままですね）

ですから条件'A[R] < A[P] + A[Q]'だけをチェックすればいいのですね。
一つでも条件全てにあうtriangularなものがあるかないかを、１か０で返せという問題ですから、あるA[R]にたいして一番大きいA[P] + A[Q]だけを調べればいいということです。（そうすれば全ての条件が成り立つものがあるということになり１を返せば良い）
ということは、連続する３つのスロットをそれぞれA[P]、A[Q]、A[R]として調べればいいですね。

またもとにもどって、なぜ、０以下の値を無視していいのかを考えましょう。

もし、 A[P] <= 0 <= A[Q] <= A[R]であったら、A[P] + A[Q] <= A[Q]になりますね。そうすると’A[P] + A[Q] <= A[Q] <= A[R]’になりますので、条件’A[R] < A[P] + A[Q]’は成り立たなくなります。ですからすべて０以下になるようなPは全て無視していいのです。

この方針で100%のスコアになります。O(N log (N))の時間的な計算量を指定されているので、マージ・ソートなどを使う方が確実ですが（クイック・ソートの最悪実行時間はこれより大きい）、Cにはマージ・ソートのライブラリが標準でないので、qsortを使っています。

また、qsort用の比較関数で’return *(int*)a - *(int*)b;’とやってしまうと、アンダーフローして間違った比較がなされる事があります。同様に'r < p + q' として比較してしまうと、p　+　qがオーバーフローしてしまうので’r - p < q ’と書き換えて比較しましょう。（この辺で１００％でなかったのでハマってました…orz)

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) 
{
    if (N < 3){
        return 0;
    }
    
    qsort(A, N, sizeof(int), compare_int);
    
    int i;
    for (i = 2; i < N; i++){
        
        int p = A[i - 2];
        int q = A[i - 1];
        int r = A[i];
        
        //neglect negative values.
        if (p <= 0){
            continue;
        }

        //if write like 'r < p + q', 'p + q' may overflow.
        if (r - p < q ){
            return 1;
        }
    }
    
    return 0;
}