1. 問題
高速性が要求される問題のひとつ。N (3<=N<=5000) 個の入力データから、任意の3つ (x, y, z) を選んで、x+y=z となるTripleの数を求めよ。
なお、入力データはすべて正の整数、32ビット範囲内に収まる。プログラムの実行制限時間が8秒。

2. 実例
次の入力データをみてみる。
1 2 3 4 5 6

1+2=3, 1+3=4, 1+4=5, 1+5=6, 2+3=5, 2+4=6 になるので、答えは6になる。

3. 計算法
入力データの個数が5000までなので、一見簡単に解けそうだが、やってみて、大変さが分かった。出題者の意図は O(n^2) アルゴリズムの提出にある。

自分の順位は現時点では18位なので、まだまだ改善するところを考えないといけないが、つぎのような方法でやってきた。

入力したデータに対し、ソートを行い、グループ化を行う。グループ化というのは、同じ値の入力データをまとめることだ。たとえば、1 1 1 2 2 3 3 という入力データを (1,3) (2,2) (3,2) にクループ化する。ソートにはO(nlogn)、グループ化には O(n) で済むが、ソートの高速化は問題として残っている。

次に、ソートされ、グループ化されたデータに対し、Tripleの数を算出する。

言葉で説明するのが面倒なので、ソースプログラムを使う。勿論分かりやすくするため、一部を書き換えているし、もっと高速化できるところもある。この部分の実行時間はO(n^2)。なお、ans変数は64ビット整数(long long int)でないとオーバーフローになってしまう。

typedef long long llong;
#define SIZE  5000
int N;
unsigned data[SIZE+5];  /* 入力データ(ソート済み) */
int freq[SIZE+5];  /* 同じ値を持つ入力データの個数 */
ans = 0;
if (N == 1) { puts("0"); exit(1); }
for (k = 1; k < N; k++) {
    i = 0; j = k-1;
    while (i < j) {
        if (data[i]+data[i] == data[k]) {
            ans += (llong)freq[i]*(freq[i]-1)/2*freq[k];
            break;
        }
        if (data[j]+data[j] == data[k]) {
            ans += (llong)freq[j]*(freq[j]-1)/2*freq[k];
            break;
        }
        if (data[i]+data[j] == data[k]) {
            ans += ((llong)freq[i])*freq[j]*freq[k];
            i++, j--;
        } else if (data[i]+data[j] &lt; data[k]) i++;
        else j--;
    }
}
printf("140733424702768\n", ans);

4. スピードの改善
スピードを上げるために、データのソートとグループ化に、2分探索木を使ってみた。順位は14に上がったが、劇的な改善にまだ繋がっていない。最後のtriple数の計算がボトルネックになっているから。

2分検索(バイナリサーチ)のような手法が使えるのではないか、そんな気がしている。ランク1位の時間は0.540秒なので、自分としてはせめて1秒を切りたい。

Comments are closed.

Post Navigation