문제

문제 분석

Naive한 방법은 모든 a, b, c, d 조합을 시도해보는 것이다.
다만, 시간복잡도가 O(N^4) 이기 때문에 제한시간 내에 풀 수 없다.
Naive한 풀이를 조금더 살펴보면 (0,0,*,*), (0,1,*, *) 만 살펴봐도 중복해서 c, d를 전수 조사하고 있다.
앞으로도 계속 필요한 (c,d) 조합을 저장해 놓고 사용하면 좋을 것 같다.

(a,b) 조합을 전수조사 하면서, 미리 계산된 필요한 (c,d) 조합을 binary search로 찾을 수 있겠다.
시간 복잡도는 O(N^2 * 2logN)이 된다.

12초라는 제한 시간 내에 풀기에는 충분한 복잡도이다.

(다른 풀이로는 two pointer로도 풀 수 있을 것 같다.)

알고리즘

• binary search

자료구조

• vector<int>

결과

필요한 값을 unordered_map으로 찾을 수 있지 않을까 싶었다.
시간 초과로 실패하였다.
최대 key가 16,000,000이 되므로 collision이 발생할 여지가 많아, O(1)보다 느리게 작동한 것으로 보인다.

vector + binary search로 푸니 시간 내에 풀렸다.

unordered_map

/* NOTE:
map의 O(logN)보다 unordered_map의 O(1)이 빨라 undordered_map을 썻다.
그러나, unordered_map같은 경우에도, collision이 많은 경우 O(1)보다 느려질 수 있다.
충돌이 많이 생길 가능성이 존재하다면 사용하지 말자.

또한 map의 operator[]도 디테일하게 알아두자.
*/
#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

const int MAX_N = 4000;
const int NUM_OF_ARR = 4;

int N;
vector<vector<int>> arr(NUM_OF_ARR, vector<int>(MAX_N,0)); // [arr:a,b,c,d][idx]
unordered_map<int, int> m; // key: sum, val: count;

int main( void )
{
  ios_base::sync_with_stdio(false); cin.tie(NULL); 

  cin >> N;
  for ( int i = 0; i < N; i++ ){
      cin >> arr[0][i]
          >> arr[1][i]
          >> arr[2][i]
          >> arr[3][i];
  }

  for ( int ci = 0; ci < N; ci++ ){
      for ( int di = 0; di < N; di++ ){
          m[arr[2][ci] + arr[3][di]]++;
      }
  }

  int64_t ans = 0;
  for ( int ai = 0; ai < N; ai++ ){
      for ( int bi = 0; bi < N; bi++ ){
          int trg = -(arr[0][ai] + arr[1][bi]);
          if ( m.find(trg) != m.end() )
              ans += m[trg];
      }
  }

  cout << ans;

  return 0;
}

vector + binary search

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_N = 4000;
const int NUM_OF_ARR = 4;

int N;
vector<vector<int>> arr(NUM_OF_ARR, vector<int>(MAX_N,0)); // [arr:a,b,c,d][idx]
vector<int> sumAB;
vector<int> sumCD;

int main( void )
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); 

    cin >> N;
    for ( int i = 0; i < N; i++ ){
        cin >> arr[0][i]
            >> arr[1][i]
            >> arr[2][i]
            >> arr[3][i];
    }

    sumAB.resize(N*N,0);
    sumCD.resize(N*N,0);
    for ( int i = 0; i < N; i++ ){
        for ( int j = 0; j < N; j++ ){
            sumAB[i*N+j] = arr[0][i] + arr[1][j];
            sumCD[i*N+j] = arr[2][i] + arr[3][j];
        }
    }
    sort(sumAB.begin(), sumAB.end() );
    sort(sumCD.begin(), sumCD.end() );

    for ( int i = 0; i < N*N; i++ ){
        printf("sumAB: %d, \t sumCD: %d\n", sumAB[i], sumCD[i]);
    }
    int64_t ans = 0;
    int l = 0;
    int r = N*N-1;
    while ( l < N*N && r >= 0 ){
        int lup = upper_bound(sumAB.begin(), sumAB.end(), sumAB[l] ) - sumAB.begin() - 1;
        int rlow = lower_bound(sumCD.begin(), sumCD.end(), sumCD[r] ) - sumCD.begin(); 
        printf("l, lup, r, rlow, sab, scd: %d, %d, %d, %d, %d, %d\n", l, lup, r, rlow, sumAB[l], sumCD[r]);

        if ( sumAB[l] + sumCD[r] == 0){
            ans += int64_t(lup-l+1) * int64_t(r - rlow + 1);
            if ( r > 0 )
                r = rlow - 1;
            else 
                l = lup + 1;
        }
        else if ( sumAB[l] + sumCD[r] > 0 ){
            r = rlow - 1;
        }   
        else { // sum < 0
            l = lup + 1;                
        }
    }

    cout << ans;

    return 0;
}

Other

unoredered_map 은 O(1)으로 매우 빠르지만, collision이 많으면 느려진다.
특히, 이번 문제는 key가 16,000,000개로 많기 때문에 collision이 발생할 여지가 많다.