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