1

このCodeChefの課題を解決したい：

N個の（範囲100,000個の）要素の配列Aが与えられたとします。

Aj-Ai = Ak- Aj and i < j < k

つまり、Ai、Aj、Akが等差数列になるように、1 <= Ai、Aj、Ak<=30,000の3つの要素のすべてのペアの数を求めます。たとえば、配列の場合：

9 4 2 3 6 10 3 3 10


したがって、APは次のとおりです。

{2,6,10},{9,6,3},{9,6,3},{3,3,3},{2,6,10}


したがって、必要な答えは5です。

私のアプローチ

私が試したのは、過去と右という名前の30,000個の長い配列を取得することです。最初に右には、各1〜30,000要素の数が含まれます。

i番目の位置にいる場合、pastはiの前の配列値のカウントを格納し、rightはiの後の配列のカウントを格納します。配列内の考えられるすべての一般的な違いをループするだけです。コードは次のとおりです。

right[arr[1]]--;

for(i=2;i<=n-1;i++)
{
    past[arr[i-1]]++;
    right[arr[i]]--;
    k=30000 - arr[i];
    if(arr[i] <= 15000)
        k=arr[i];
    for(d=1;d<=k;d++)
    {
        ans+= right[arr[i] + d]*past[arr[i]-d] + past[arr[i] + d]*right[arr[i]-d];
    }
    ans+=past[arr[i]]*right[arr[i]];
}



しかし、これは私に制限時間を超えさせます。より良いアルゴリズムを手伝ってください。

4

2 に答える 2

3

リストを最初に通過し、3タームAPが可能な数のペアのみを抽出すると、実行時間を大幅に短縮できます（差は0 mod 2です）。そして、そのようなペアの間で反復します。

疑似C++-yコード：

// Contains information about each beginning point
struct BeginNode {
  int value;
  size_t offset;
  SortedList<EndNode> ends;  //sorted by EndNode.value
};

// Contains information about each class of end point
struct EndNode {
  int value;
  List<size_t> offsets; // will be sorted without effort due to how we collect offsets
};

struct Result {
  size_t begin;
  size_t middle;
  size_t end;
};

SortedList<BeginNode> nodeList;
foreach (auto i : baseList) {
  BeginNode begin;
  node.value = i;
  node.offset = i's offset; //you'll need to use old school for (i=0;etc;i++) with this
  // baseList is the list between begin and end-2 (inclusive)
  foreach (auto j : restList) { 
    // restList is the list between iterator i+2 and end (inclusive)
    // we do not need to consider i+1, because not enough space for AP
    if ((i-j)%2 == 0) { //if it's possible to have a 3 term AP between these two nodes
      size_t listOffset = binarySearch(begin.ends);
      if (listOffset is valid) {
        begin.ends[listOffset].offsets.push_back(offsets);
      } else {
        EndNode end;
        end.value = j;
        end.offsets.push_back(j's offset);
        begin.ends.sorted_insert(end);
      }
    }
  }
  if (begin has shit in it) {
    nodeList.sorted_insert(begin);
  }
}
// Collection done, now iterate over collection

List<Result> res;
foreach (auto node : nodeList) {
  foreach (auto endNode : node.ends) {
    foreach (value : sublist from node.offset until endNode.offsets.last()) {
      if (value == average(node.value, endNode.value)) {
        // binary_search here to determine how many offsets in "endNode.offsets" "value's offset" is less than.
        do this that many times:
          res.push_back({node.value, value, endNode.value});
      }
    }
  }
}

return res;
于 2012-11-05T21:10:55.013 に答える
1

これは、Ai+Akを利用するソリューションの単純なCバージョンです。テストする必要があります。

#include <stdio.h>

static int arr[] = {9, 4, 2, 3, 6, 10, 3, 3, 10};

int main ()
{
    int i, j, k;
    int sz = sizeof(arr)/sizeof(arr[0]);
    int count = 0;

    for (i = 0; i < sz - 2; i++)
    {
        for (k = i + 2; k < sz; k++)
        {
            int ik = arr[i] + arr[k];
            int ikdb2 = ik / 2;

            if ((ikdb2 * 2) == ik) // if ik is even
            {
                for (j = i + 1; j < k; j++)
                {
                    if (arr[j] == ikdb2)
                    {
                        count += 1;
                        printf("{%d, %d, %d}\n", arr[i], arr[j], arr[k]);
                    }
                }
            }
        }
    }
    printf("Count is: %d\n", count);
}

とコンソールドリブル：

tmp e$ cc -o triples triples.c
tmp e$ ./triples
{9, 6, 3}
{9, 6, 3}
{2, 6, 10}
{2, 6, 10}
{3, 3, 3}
Count is: 5
tmp e$

このより複雑なバージョンでは、値でインデックス付けされたAjのリストが保持され、n-cubedからn-squared（ちょっと）になります。

#include <stdio.h>
#include <stdint.h>

static uint32_t arr[] = {9, 4, 2, 3, 6, 10, 3, 3, 10};

#define MAX_VALUE 100000u
#define MAX_ASIZE  30000u

static uint16_t index[MAX_VALUE+1];
static uint16_t list[MAX_ASIZE+1];

static inline void remove_from_index (int subscript)
{
    list[subscript] = 0u; // it is guaranteed to be the last element

    uint32_t value = arr[subscript];

    if (value <= MAX_VALUE && subscript == index[value])
    {
        index[value] = 0u; // list now empty
    }
}

static inline void add_to_index (int subscript)
{
    uint32_t value = arr[subscript];

    if (value <= MAX_VALUE)
    {
        list[subscript] = index[value]; // cons
        index[value] = subscript;
    }
}

int main ()
{
    int i, k;
    int sz = sizeof(arr)/sizeof(arr[0]);
    int count = 0;

    for (i = 0; i < sz - 2; i++)
    {
        for (k = i; k < sz; k++) remove_from_index(k);

        for (k = i + 2; k < sz; k++)
        {
            uint32_t ik = arr[i] + arr[k];
            uint32_t ikdb2 = ik / 2;

            add_to_index(k-1); // A(k-1) is now a legal middle value 

            if ((ikdb2 * 2) == ik) // if ik is even
            {
                uint16_t rover = index[ikdb2];

                while (rover != 0u)
                {
                    count += 1;
                    printf("{%d, %d, %d}\n", arr[i], arr[rover], arr[k]);

                    rover = list[rover];
                }
            }
        }
    }
    printf("Count is: %d\n", count);
}

とドリブル：

tmp e$ cc -o triples triples.c
tmp e$ ./triples
{9, 6, 3}
{9, 6, 3}
{2, 6, 10}
{2, 6, 10}
{3, 3, 3}
Count is: 5
tmp e$
于 2012-11-05T23:01:13.820 に答える