SPOJ 4580 ABCDEF

SPOJを始めました

問題
http://www.spoj.com/problems/ABCDEF/

解法
式を
ab + c = (f + e)d
と変形すると二分探索が使える。右辺の値を決めて、左辺の値をにぶたんするとやりやすいと思う。
計算量は
O(N^3 log (N^3) ) = O(N^3 log N)
となる。

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 100;
int s[MAX];
int abc[MAX * MAX * MAX];
int fed[MAX * MAX * MAX];

int main(){
	int n;
	int fed_n = 0;
	scanf("%d", &n);
	for(int i = 0; i < n; i++)
		scanf("%d", &s[i]);
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			for(int k = 0; k < n; k++)
				abc[i * n * n + j * n + k] = s[i] * s[j] + s[k];
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			for(int k = 0; k < n; k++){
				if(s[k] == 0) continue;
				fed[fed_n] = (s[i] + s[j]) * s[k];
				fed_n++;
			}
		}
	}
	sort(abc, abc + n*n*n);
	sort(fed, fed + fed_n);
	long long ans = 0;
	for(int i = 0; i < fed_n; i++){
		int *p = lower_bound(abc, abc + n*n*n, fed[i]);
		int *q = upper_bound(abc, abc + n*n*n, fed[i]);
		ans += distance(p, q);
	}
	printf("%lld\n", ans);
	return 0;
}