[C++] 14756번 Telescope

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

---

 

26/02/12

 

 

이동 문제와 거의 유사한 문제이다.

---

 

문제 접근 방식:

 

 

일단 움직일 배열을 뒤집어주자.

이후 각 행 별로 Convolution을 적용하면 행 별끼리의 결과가 나온다.

우리가 구하는 sum은 행 별 연산 결과를 하나의 열에 대해서 더한 것이기 때문에, 그렇게 구한 sum이 문제에서 주어진 $W$보다 클 경우에만 답에 $+1$을 해주면 된다. 

---

아래는 내가 위의 접근 방식과 같이 작성한 C++ 코드이다. 더보기를 누르면 확인할 수 있다.

// 14756번 Telescope
// FFT
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'

struct FFT {
    using ld = long double;
    using ll = long long;
    static constexpr ld PI = acosl(-1.0L);
private :
    // HELPER struct
    struct cd {
        ld re, im;
        cd(ld r=0, ld i=0): re(r), im(i) {}
        cd operator + (const cd& o) const { return cd(re+o.re, im+o.im); }
        cd operator - (const cd& o) const { return cd(re-o.re, im-o.im); }
        cd operator * (const cd& o) const { return cd(re*o.re - im*o.im, re*o.im + im*o.re); }
        cd& operator += (const cd& o) { re+=o.re; im+=o.im; return *this; }
        cd& operator -= (const cd& o) { re-=o.re; im-=o.im; return *this; }
        cd& operator *= (const cd& o) { *this = (*this)*o; return *this; }
    };
public : 
    void iterative_FTT(vector<cd>& a, int invert){
        int n = (int)a.size();
        // 1) bit-reversal permutation
        for (int i = 1, j = 0; i < n; i++){
            int bit = n >> 1;
            while (j & bit){
                j ^= bit;
                bit >>= 1;
            }
            j ^= bit;
            if (i < j) swap(a[i], a[j]);
        }
        // 2) butterflies by length = 2, 4, 8, ...
        for (int len = 2; len <= n; len <<= 1){
            ld ang = 2 * PI / len * (invert ? -1 : 1);
            cd w_len(cosl(ang), sinl(ang)); // primitive len-th root of unity on unit circle
            for (int i = 0; i < n; i += len){
                cd w(1, 0);
                for (int j = 0; j < len / 2; j++){
                    cd u = a[i+j];
                    cd v = w * a[i+j+len/2];
                    a[i+j] = u+v;
                    a[i+j+len/2] = u-v;
                    w *= w_len;
                }
            }
        }
        // 3) Divide by n (multiply by inverse) for inverse transform
        if (invert){
            ld inv_n = 1.0L / n;
            for (int i = 0; i < n; ++i){
                a[i].re *= inv_n;
                a[i].im *= inv_n;
            }
        }
    }
    // Input : Coefficient vector {a_0, a_1, ...}, {b_0, b_1, ...}
    // Output : Convolution of two coefficient vector
    vector<ll> convolution(const vector<ll>& a, const vector<ll>& b) {
        if (a.empty() || b.empty()) return {};
        int S_a = (int)a.size(), S_b = (int)b.size();
        // Make vector size easy to dnc(2^n).
        int n = 1;
        while (n < S_a + S_b - 1){
            n <<= 1;
        }
        vector<cd> fa(n), fb(n);
        for (int i = 0; i < S_a; i++) fa[i] = cd((ld)a[i], 0);
        for (int i = 0; i < S_b; i++) fb[i] = cd((ld)b[i], 0);
        // FTT
        iterative_FTT(fa, 0); iterative_FTT(fb, 0);
        // Pointwise product
        for (int i = 0; i < n; i++) fa[i] *= fb[i];
        // IFTT
        iterative_FTT(fa, 1);
        vector<ll> res(S_a + S_b - 1);
        for (int i = 0; i < res.size(); i++) {
            res[i] = (ll) llround(fa[i].re); // rounding to nearest integer
        }
        return res;
    }
};

int main() {
    fastio

    long long N, l, m, W;
    cin >> N >> l >> m >> W;
    vector<vector<long long>> T(m, vector<long long>(N, 0)), P(m, vector<long long>(l, 0));
    for (int i = 0; i < m; ++i){
        for (int j = 0; j < N; ++j){
            cin >> T[i][j];
        }
    }
    for (int i = 0; i < m; ++i){
        for (int j = 0; j < l; ++j){
            cin >> P[i][l-j-1];
        }
    }
    vector<vector<long long>> res;
    FFT fft;
    for (int i = 0; i < m; ++i){
        auto C = fft.convolution(T[i], P[i]);
        res.push_back(C);
    }
    int ans = 0;
    for (int i = l-1; i < N; ++i){
        long long sum = 0;
        for (int j = 0; j < m; ++j){
            sum += res[j][i];
        }
        if (sum > W) ++ans;
    }
    cout << ans;
    return 0;
}