10531번: Golf Bot

https://www.acmicpc.net/problem/10531

FFT를 이용하여 해결한다.
구현은 http://cubelover.tistory.com/19를 참고했다.

시간복잡도는 $O(n\lg n)$

#include<cstdio>
#include<complex>
using namespace std;
const int sz = 1 << 19;
int n, m, x, r;
complex<double> a[sz] = { 1 };
void FFT(int inv) {
    for (int i = 0; i < sz; i++) {
        int j = 0;
        for (int k = 0; 1 << k < sz; k++) j = j << 1 | i >> k & 1;
        if (i < j) swap(a[i], a[j]);
    }
    for (int i = 1; i < sz; i <<= 1) {
        complex<double> w = polar(1.0, inv * acos(-1) / i);
        for (int j = 0; j < sz; j += i << 1) {
            complex<double> b = 1;
            for (int k = j; k < j + i; k++) {
                complex<double> u = a[k], v = b*a[k + i];
                a[k] = u + v;
                a[k + i] = u - v;
                b *= w;
            }
        }
    }
}
int main() {
    for (scanf("%d", &n); n--;) scanf("%d", &x), a[x] = 1;
    FFT(1);
    for (int i = 0; i < sz; i++) a[i] *= a[i];
    FFT(-1);
    for (int i = 0; i < sz; i++) a[i] /= sz;
    for (scanf("%d", &m); m--;) scanf("%d", &x), r += real(a[x]) >= 0.5;
    printf("%d", r);
    return 0;
}

13575번: 보석 가게

https://www.acmicpc.net/problem/13575


FFT 아닌 풀이

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
vector<pair<int, int> > v = { { 0,-1 },{ 1,1 } };
int n, k, a[1000];
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++) scanf("%d", a + i);
    for (int i = 0; i < k; i++) {
        vector<pair<int, int> > t;
        for (int j = 0; j < n; j++)
            for (auto it : v) t.push_back({ it.first + a[j],it.second });
        sort(t.begin(), t.end());
        v.clear();
        int s = t[0].second;
        v.push_back(t[0]);
        for (int j = 1; j < t.size(); j++) {
            s += t[j].second;
            if (!s) {
                v.push_back(t[j]);
                if (j != t.size() - 1) v.push_back(t[j + 1]);
            }
        }
    }
    for (int i = 0; i < v.size(); i += 2)
        for (int j = v[i].first; j < v[i + 1].first; j++) printf("%d ", j);
    return 0;
}