猫でもわかるWeb開発・プログラミング

本業エンジニアリングマネージャー。副業Webエンジニア。Web開発のヒントや、副業、日常生活のことを書きます。

トップ > AtCoder Typical Contest #001 C - 高速フーリエ変換 を解いた

AtCoder Typical Contest #001 C - 高速フーリエ変換 を解いた

はじめに

どうも、yoshikyotoです。 本番で頑張って実装した高速フーリエ変換、ちょっと直したら通ったので貼っておきます。

間違っていた点

  • 2の冪乗とは、2, 4, 8, 16, ... のことであるが、2の冪乗ではなく、1つ前の数字の2乗を求めていた（2, 4, 16, 256, ...）ため、数字が大きくなりすぎてTLEしていた
  • 最終的に real() の切り捨てを出力していたが、そこの誤差で死んでいた？四捨五入にしたら通った。ここはよく分かっていないので要復習

実装

本当はJavaで実装したかったけど、C++の complex が便利だったのでこれを使用。 気が向いたり、必要に迫られたらJavaでも実装します。 #include <complex> してください。

高速フーリエ変換部分

// 高速フーリエ変換
// inverse = 1 でフーリエ変換、inverse = -1 で逆フーリエ変換
const double PI = 4.0*atan(1.0);
const complex<double> I(0,1);
void fft(complex<double> a[], int n, int inverse) {
    double theta = 2 * inverse * PI / n;
    
    for (int m = n; m >= 2; m >>= 1) {
        int mh = m >> 1;
        for (int i = 0; i < mh; i++) {
            complex<double> w = exp(i*theta*I);
            for (int j = i; j < n; j += m) {
                int k = j + mh;
                complex<double> x = a[j] - a[k];
                a[j] += a[k];
                a[k] = w * x;
            }
        }
        theta *= 2;
    }
    int i = 0;
    for (int j = 1; j < n - 1; j++) {
        for (int k = n >> 1; k > (i ^= k); k >>= 1);
        if (j < i) swap(a[i], a[j]);
    }
    
    if(inverse == -1){
        complex<double> d(n,0);
        REP(i,n){
            a[i] = a[i] / d;
        }
    }
}

main関数

離散フーリエ変換による乗算の部分

int main(int argc, const char * argv[]){
    int n;
    cin >> n;
    int g[100000], h[100000];
    REP(i,n){
        cin >> g[i] >> h[i];
    }
    
    int nn = 1;
    while(nn <= n + n - 1){
        nn *= 2;
    }
    
    complex<double> *gg = new complex<double>[nn];
    complex<double> *hh = new complex<double>[nn];
    REP(i,nn){
        if(i < n){
            gg[i] = g[i];
            hh[i] = h[i];
        }else{
            gg[i] = 0;
            hh[i] = 0;
        }
    }
    fft(gg, nn, 1);
    fft(hh, nn, 1);
    
    complex<double> *ff = new complex<double>[nn];
    REP(i,nn){
        ff[i] = gg[i] * hh[i];
    }
    fft(ff, nn, -1);
    cout << 0 << endl;
    REP(i, 2*n-1){
        cout << (ff[i].real()) << endl;
    }
}

参考