5

アルゴリズムに関する 1 つの質問に行き詰まりました。以下の問題に対する効率的なアルゴリズムを提案してください。

質問は

合計が指定された数で割り切れる部分配列の数を見つけます。

私の仕事

複雑さが O(N^2) の 1 つのアルゴリズムを作成しました。ここでは、N = 配列のサイズです。

マイコード

#include<stdio.h>

using namespace std;

 main() {
    int N;
    int P;
    int T;
    int val;
    long long int count = 0;
    long long int answer = 0;
    scanf("%d", &T);
    //T = 20;

    for(int k = 1; k <= T; k++) {
        scanf("%d", &N);
        scanf("%d", &P);
        count = 0;
        answer = 0;
        for(int i = 0; i < N; i++) {
            scanf("%d", &val);
            count += val;
            workingArray[i] = count;
        }

        for(int length = 1; length <= N; length++) {
            for(int start = 0; start <= (N-length); start++) {
                if( start == 0 ) {
                    if(workingArray[start+length-1]%P == 0) answer++;
                }
                else if( (workingArray[start+length-1] - workingArray[start-1])%P == 0) answer++;
            }
        }

        printf("Case #%d\n%lld\n", k, answer);
    }
    return 0;
 }
4

2 に答える 2

27

与えられた数に対してX...

基本的な考え方: (正確性の非公式な証明付き)

範囲内の数値の合計が で[a, b]割り切れる場合、次のようになりますX。

(∑<sub>i=1 to a-1input[i]) % X = (∑<sub>i=1 to binput[i]) % X

より数学的な用語では：

the sum from the first element to b = the sum from the first element to a
                                    + the sum of the elements between the two

そう：

the sum of the elements between the two = the sum from the first element to b
                                        - the sum from the first element to a

次に、右辺の合計を で割ったときの余りが同じ場合X、余りは相殺され、2 つの間の要素の合計は で割り切れXます。詳細：

C = the sum of the elements between the two
B = the sum from the first element to b
A = the sum from the first element to a

これで、いくつかの整数、、およびについて、とのB形式に変換できます。ここで、定義により、とはとで割った余りになります。PX + QARX + SPQRS0 <= Q, S < XQSBAX

次に、次のようになります。

C = (PX + Q) - (RX + S)
C = PX + Q - RX - S
C = PX - RX + Q - S
C = (P-R)X + Q - S

明らか(P-R)Xに で割り切れXます (結果は単純に です(P-R))。Q - Sで割り切れる必要があるだけですXが、 であるため0 <= Q, S < X、等しい必要があります。

例：

B = 13、、とA = 7しましょうX = 3。

ここB % X = 1とA % X = 1.

とのBように書き換えることができます。4*3 + 1A2*3 + 1

次にC = 4*3 + 1 - 2*3 - 1 = 2*3、これは で割り切れ3ます。

高レベルのアプローチ:

のハッシュ マップを作成しますkey -> value。ここで、各値は、配列の先頭から開始して特定の位置に到達できる方法の数を表しますsum mod X = key(以下の例の "Mod 3" 行とマップ値を参照)。 ）。

ここで、上記のロジックに基づいて、2 つの部分配列が最初から始まり、位置aでbそれぞれ終わる場合、両方とも同じ を持つ場合sum mod X、部分配列[a, b]は で割り切れることがわかりXます。

したがって、ハッシュマップの各値は、可能な開始点と終了点のセットのサイズを表します。これにより、割り切れる部分配列が得られXます (任意の点が開始点または終了点のいずれかになります)。

これらの開始点と終了点を選択する可能な方法の数は単純です
value choose 2 = value!/(2*(value-2)!)(値が 1 の場合は 0)。

したがって、ハッシュマップの各値についてそれを計算し、それらをすべて合計して、 で割り切れる部分配列の数を取得しXます。

アルゴリズム：

これまでのすべての数値の累積合計を格納するハッシュ マップをmod X作成し、残りの値が出現する頻度のカウントにマップします ( expected で作成されますO(n))。

の値を 1増やし0ます - これは配列の開始に対応します。

カウントを 0 に初期化します。

ハッシュ マップの値ごとvalue!/(2*(value-2)!)に、カウントに追加します。

カウントは目的の値です。

実行時間：

予想されるO(n)。

例：

Input:    0  5  3  8  2  1
X = 3

Sum:   0  0  5  8 16 18 19
Mod 3: 0  0  2  2  1  0  1

Map:
  0 -> 3
  1 -> 2
  2 -> 2

Count = 3! / 2*(3-2)! = 3  +
        2! / 2*(2-2)! = 1  +
        2! / 2*(2-2)! = 1
      = 5

サブアレイは次のようになります。

0  5  3  8  2  1
-                     0                 =  0 % 3 = 0
-------------         0 + 5 + 3 + 8 + 2 = 18 % 3 = 0
   ----------         5 + 3 + 8 + 2     = 18 % 3 = 0
      -               3                 =  3 % 3 = 0
            ----      2 + 1             =  3 % 3 = 0
于 2013-10-23T12:25:13.083 に答える