[C++] 1067번 이동 - 수학, FFT

1067번 이동

1. 문제

• N개의 수로 이루어진 배열 X, Y가 주어진다. 이때 배열은 순환이동이 가능하다. (ex: {1, 2, 3} -> {3, 1, 2}) 점수 S는 아래와 같이 계산한다.
• \(S=\sum_{i=1}^{N}X[i]\cdot Y[i]\)
• S의 최댓값을 구하여라.

입력

• -1- : 배열의 크기 \(N(1 \leq N \leq 60,000)\)
• -1- : 배열 X
• -1- : 배열 Y \((0 \leq x, y < 100)\)

출력

• -1-: S의 최댓값

2. 재정의

• X

3. 해결 방법

• X 배열의 값을 차례대로 계수로 갖는 다항식을 f라고 하자. Y 배열의 값을 역방향으로 계수로 갖는 다항식을 g라고 하자. X와 Y를 곱하면 X 배열의 값과 Y 배열의 곱을 나타내는 항이 N개 만들어지는데 이는 모두 차수가 i 또는 N+i이다.
• 즉 f와 g를 FFT로 곱해준 후 차수가 i 또는 N+i가 되는 계수를 합한 것이 하나의 S의 값이 되는 것이다.
• i를 0부터 N-1까지 증가시켜 가며 모든 S값을 비교하면 S의 최댓값을 구할 수 있다.

4. 실수한 점, 개선할 점

• X

 

<코드>

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <complex>

using namespace std;

typedef complex<double> cpx;
typedef vector<cpx> vcpx;

const double pi = acos(-1);

const int MAX_N = 60000;

// <문제>
int N;
// 배열 X, Y
vcpx x, y;

// Fast Fourier Transform
void FFT(vcpx &f, bool inv) {
    int n = (int)f.size();
    
    vcpx ftmp(f);
    for(int i=0; i<n; i++) {
        int bz = n, shift = 0, idx = i;
        while(bz > 1) {
            if(idx & 1) shift += bz >> 1;
            idx >>= 1;
            bz >>= 1;
        }
        f[shift + idx] = ftmp[i];
    }
    
    for(int i=1; i<n; i <<= 1) {
        double x = inv ? -pi/i : pi/i;
        cpx w(cos(x), sin(x));
        for(int j=0; j<n; j += i << 1) {
            cpx wp(1, 0);
            for(int k=0; k<i; k++) {
                cpx tmp = wp * f[i+j+k];
                f[i+j+k] = f[j+k] - tmp;
                f[j+k] += tmp;
                wp *= w;
            }
        }
    }
    
    if(inv)
        for(int i=0; i<n; i++)
            f[i] /= cpx(n, 0);
}

// 두 다항식의 계수를 입력받아 그 곱의 계수를 반환
vcpx pol_mul(vcpx a, vcpx b) {
    int n=1;
    while((n <= a.size()) || (n <= b.size())) n <<= 1;
    n <<= 1;
    a.resize(n); b.resize(n);
    
    FFT(a, false); FFT(b, false);
    for(int i=0; i<n; i++)
        a[i] *= b[i];
    FFT(a, true);
    
    return a;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> N;
    vcpx xv(MAX_N+1), yv(MAX_N+1);
    
    // x배열을 계수로 하는 다항식과, y배열을 역방향으로 계수로 하는 다항식 생성.
    for(int i=0; i<N; i++) {
        int x;
        cin >> x;
        xv[i] = x;
    }
    for(int i=0; i<N; i++) {
        int y;
        cin >> y;
        yv[N-1-i] = y;
    }
    
    // 두 다항식을 곱하면 같은 순서로 곱해진 항의 차수가 모두 최대 2가지로 겹치지 않고
    // 일정하게 나와 이를 합하면 S를 구할 수 있음.
    vcpx zv = pol_mul(xv, yv);
    
    int MS = 0;
    for(int i=0; i<N; i++)
        MS = max(MS, (int)(round(zv[i].real()) + round(zv[N+i].real())));
    
    cout << MS;
}

 

<문제 바로가기>

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

1067번: 이동

 

<Fast Fourier Transform>

https://leyamon.tistory.com/entry/C-10531%EB%B2%88-Golf-Bot-%EC%88%98%ED%95%99-FFT

[C++] 10531번 Golf Bot - 수학, FFT

 

※ 궁금한 것 질문 남겨주시면 답변드리겠습니다. 좋아요 눌러주시고 편하게 질문해 주세요.