1296. 4 values whose sum is 0

いろいろとやる気でないので日記でも書くことにする。

https://www.spoj.pl/problems/SUMFOUR/

長さn(<= 4000)の整数のリストが4つ与えられる。各リストから整数を一つずつ取ってきて組を作ったとき、和が0なるような組はいくつ出来るか。

4つのリストをそれぞれA,B,C,Dと呼ぶことにする。まず、S1 = {a+b | a∈A, b∈B} および S2 = {c+d | c∈C, d∈D} を考える。このとき、S1のすべての要素s1に対して、S2に含まれる-s1の数をカウントすれば解が求まる。S1, S2 の要素数は n^2 であり、S2をソートしておけば-s1の数のカウントは二分探索を使うことにより O(log n) でできる。よって全体のオーダーは O(n^2 log n) となる。

#include <stdio.h>
#include <algorithm>
using namespace std;

int list[4][4000];
int sum[4000*4000];

int main()
{
    int n;
    scanf("%d", &n);
    int nn = n*n;
    for (int i = 0; i < n; ++i) {
        scanf("%d%d%d%d", &list[0][i], &list[1][i], &list[2][i], &list[3][i]);
    }
    int k = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            sum[k] = list[2][i] + list[3][j];
            ++k;
        }
    }
    sort(sum, sum + nn);
    int count = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            int s = list[0][i] + list[1][j];
            pair<int*, int*> range = equal_range(sum, sum + nn, -s);
            count += range.second - range.first;
        }
    }
    printf("%d\n", count);
}