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); }