最大の三角形を探す（5）

さて、元の問題をもう一度。

n本の棒があります。棒iの長さはa_iです。あなたは、それらの棒から3本を選んでできるだけ周長の長い三角形を作ろうと考えています。最大の周長を求めなさい。ただし、三角形が作れない際には0を答えとしなさい。
プログラミングコンテストチャレンジブック P.21

すぐに、ソートすればいいだけと分かりますが、次に「たいてい最も長い3つを選べば終わりだろう」と思うでしょう。前回まででそれを示しました。もちろん上位3つをソートするほうが全体をソートするより速いです。よって、3つ選んで判定して三角形でなければソートすればよいです。
ただ、これだといじわるデータではソートするだけより遅くなってしまいます。いじわるデータとは、こんな感じでしょうか。

100 60 40 20 12 8 4 2 1 1

これだと最後まで三角形ができないです。
最悪のデータだとどうなるでしょう。長さが短いほうから見ていきましょう。まず1と1です。次が1では三角形になるので2です。その次は、1+2=3です。その後は、2+3=5、3+5=8です。
これはフィボナッチ数列ですね。100までの値を取れるなら、

1 1 2 3 5 8 13 21 34 55 89

よって、11個までだと三角形が出てこない可能性があるので、12本以上の棒がある場合は上位12個を取らないといけないことがわかります。元の問題は、長さの上限は10⁶、本数の上限は100でしたが、これだと小さすぎるので、長さの上限を10⁹、本数の上限を10⁶としましょう。この大きさでは、全体をソートした場合より部分ソートのほうが60倍速くなりました。

#include <iostream>
#include <algorithm>
#include <functional>
#include <windows.h>

#pragma comment(lib, "winmm.lib")

using namespace std;

typedef long long   ll;

const int   N = (int)1e9;
const int   M = (int)1e6;

// 超手抜きだがスピードをみたいだけなので問題ない
int rand_range(int a, int b) {
    int n = rand();
    return a + (ll)n * (b - a + 1) / RAND_MAX;
}

bool is_triangle(int *a) {
    return a[0] < a[1] + a[2];
}

void init(int *a) {
    for(int n = 0; n < M; n++)
        a[n] = rand_range(1, N);
}

int min_sort_num(int n, int a = 1, int b = 1) {
    return n < b ? 2 : 1 + min_sort_num(n, b, a + b);
}

int num_iteration(int *a) {
    sort(a, a + M, greater<int>());
    for(int k = 1; k < M - 1; k++) {
        if(is_triangle(a + k - 1))
            return k;
    }
    return M - 1;
}

int num_iteration2(int *a) {
    const int   L = min_sort_num(N);
    partial_sort(a, a + L, a + M, greater<int>());
    for(int k = 1; k < L - 1; k++) {
        if(is_triangle(a + k - 1))
            return k;
    }
    return L - 1;
}

int main() {
    int *a = new int[M];
    int sum = 0;
    
    int accum_t = 0;
    for(int n = 0; n < 100; n++) {
        init(a);
        const int   t = timeGetTime();
        sum += num_iteration(a);
        accum_t += timeGetTime() - t;
    }
    cout << accum_t * 1e-3 << "s" << endl;
    
    int accum_t2 = 0;
    for(int n = 0; n < 100; n++) {
        init(a);
        const int   t = timeGetTime();
        sum += num_iteration2(a);
        accum_t2 += timeGetTime() - t;
    }
    cout << accum_t2 * 1e-3 << "s" << endl;
    cout << sum << endl;
    delete [] a;
}