1

重複の可能性:
アレイ内の 3 つの長さの AP の最速アルゴリズム カウント数

私は、CodeChef の Nov12 チャレンジから取られた次の問題に取り組んできました。3つの数値a、b、cがAPにあるかどうかを確認するための基本的な式を使用して試してみました。cb = ba、つまり2b = a + cの場合です。問題は次のとおりです。

入力の最初の行には、整数 N (3 ≤ N ≤ 100000) が含まれます。次の行には、スペースで区切られた N 個の整数 A1、A2、…、AN が含まれており、それらの値は 1 から 30000 (両端を含む) の間です。

等差数列の連続する 3 項となるような 3 組を選択する方法の数を出力します。例

入力：

10

3 5 3 6 3 4 10 4 5 2

出力: 9

説明：

トリプレットの選び方は全部で9通り

1 : (i, j, k) = (1, 3, 5), (Ai, Aj, Ak) = (3, 3, 3)

2 : (i, j, k) = (1, 6, 9), (Ai, Aj, Ak) = (3, 4, 5)

3 : (i, j, k) = (1, 8, 9), (Ai, Aj, Ak) = (3, 4, 5)

4 : (i, j, k) = (3, 6, 9), (Ai, Aj, Ak) = (3, 4, 5)

5 : (i, j, k) = (3, 8, 9), (Ai, Aj, Ak) = (3, 4, 5)

6 : (i, j, k) = (4, 6, 10), (Ai, Aj, Ak) = (6, 4, 2)

7 : (i, j, k) = (4, 8, 10), (Ai, Aj, Ak) = (6, 4, 2)

8 : (i, j, k) = (5, 6, 9), (Ai, Aj, Ak) = (3, 4, 5)

私が使用したコードは

#include<stdio.h>
int scan() {
    int p=0;
    char c;
    c=getchar_unlocked();
    while(c<'0' || c>'9')
        c=getchar_unlocked();
    while(c>='0' && c<='9'){
        p=(p<<3)+(p<<1)+c-'0';
        c=getchar_unlocked();
    }
    return(p);
}
int main() {
    int N, i, j, k, count=0;
    N=scan();
    int a[N];
    for(i=0;i<N;i++)
        a[i]=scan();
    for(i=0;i<N-2;i++)
        for(j=i+1;j<N-1;j++)
            for(k=j+1;k<N;k++)
                if(a[k]+a[i]==2*a[j])
                    ++count;
    printf("%d\n", count);
    return 0;
 }

変数の制約を見るとわかるように、高速で効率的なアルゴリズムが必要であることは明らかです。安全のために、より高速な I/O を使用しましたが、それでもプログラムは時間切れになりました。ネストされた 3 つのループを使用しているため、アルゴリズムがそれほど効率的でないことは明らかです。いくつかの k の数を減らすもう 1 つの方法は、一致が見つかったらすぐに k' ループを中断することです。++count 未満であり、それは機能していますが、問題が必要とするほど効率的ではありません。

これを行うための高速なアルゴリズムを教えてください。または、AP トリプレットをより迅速に見つけるためにここで数学的な定理を学ぶことができるかどうか教えてください。

4

1 に答える 1

0

配列は必要ないと思います。

方程式からbを解く2b=a+cと、結果は 次のようになります。

b = (a + c) / 2

4つの変数を使用します： a, b, c, and counter。

  1. a, b, c3つの値を読み取って初期化します。
  2. （a + c）/ 2 == bの場合、カウンターをインクリメントし、a、b、cを出力します。
  3. シフト変数：a = b、b=c。
  4. cin >> c do：
  5. （a + c）/ 2 == bの場合、カウンターをインクリメントし、a、b、cを出力します。
  6. シフト変数：a = b、b = c;
  7. 終わり-ながら。
  8. カウンタの出力値。

私には非常に効率的に見えます。

于 2012-11-10T19:06:00.780 に答える