naoya_t@hatenablog

いわゆるチラシノウラであります

〈ARC埋め〉AtCoder Typical Contest 001

ARCじゃないけど典型と聞いて
2015/6/6開催の典型コンテスト(第1回)の問題を解いてみた
AtCoder Typical Contest 001 - AtCoder

DFSとUnionFindはやるだけ
問題はFFT

A - 深さ優先探索

(DFS)
再帰的に

// 貼付コードは若干整理してあります
#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> ii;

#define rep(var,n)    for(int var=0;var<(n);++var)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))

int H, W;
vector<string> mp;

bool dfs(int r, int c){
    assert(IN(r,0,H-1) && IN(c,0,W-1));
    switch (mp[r][c]) {
        case '#': case 'v': return false;
        case 'g': return true;
        case 's': case '.':
            mp[r][c] = 'v';
            if (0 <= r-1 && dfs(r-1,c)) return true;
            if (r+1 < H && dfs(r+1,c)) return true;
            if (0 <= c-1 && dfs(r,c-1)) return true;
            if (c+1 < W && dfs(r,c+1)) return true;
            return false;
    }
}

bool solve_dfs() {
    ii start, goal;
    rep(r,H) rep(c,W){
        switch (mp[r][c]) {
            case 's': start = ii(r,c); break;
            case 'g': goal = ii(r,c); break;
            default: break;
        }
    }
    return dfs(start.first, start.second);
}

int main() {
    cin >> H >> W;
    mp.resize(H);
    rep(r,H) cin >> mp[r];
    cout << (solve_dfs() ? "Yes" : "No") << endl;
    return 0;
}

→AC
https://beta.atcoder.jp/contests/atc001/submissions/2582268

スタックオーバーフロー回避の練習のため、再帰じゃなくてスタックを使って書いてみる。
dfs(上) || dfs(下) || dfs(左) || dfs(右) みたいなのどう書く?と暫く悩んだけど
1つでもgoalに到達したらその時点でループを抜けていいのだからただ単にスタックに調べたい位置を列挙して積んでいくだけでいい

#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> ii;
#define rep(var,n)    for(int var=0;var<(n);++var)

bool solve_dfs(int H, int W, vector<string>& mp) {
    ii start, goal;
    rep(r,H) rep(c,W){
        switch (mp[r][c]) {
            case 's': start = ii(r, c); break;
            case 'g': goal = ii(r, c); break;
            default: break;
        }
    }

    stack<ii> st;
    st.push(start);

    while (!st.empty()) {
        ii x = st.top(); st.pop();
        int r = x.first, c = x.second;
        switch (mp[r][c]) {
            case '#': case 'v': break;
            case 'g': return true;
            case 's': case '.':
                mp[r][c] = 'v';
                if (0 <= r-1) st.push(ii(r-1, c));
                if (r+1 < H) st.push(ii(r+1, c));
                if (0 <= c-1) st.push(ii(r, c-1));
                if (c+1 < W) st.push(ii(r, c+1));
                break;
        }
    }
    return false;
}

int main() {
    int H, W; cin >> H >> W;
    vector<string> mp(H);
    rep(r,H) cin >> mp[r];
    cout << (solve_dfs(H,W,mp) ? "Yes" : "No") << endl;
    return 0;
}

→AC
https://beta.atcoder.jp/contests/atc001/submissions/2583013

B - UnionFind

繋ぐだけ

#include <bits/stdc++.h>
using namespace std;

#define rep(var,n)    for(int var=0;var<(n);++var)

class UnionFind {
    vector<int> data;
 public:
    UnionFind(int size) : data(size, -1) { }
    bool unionSet(int x, int y) {
        x = root(x); y = root(y);
        if (x != y) {
            if (data[y] < data[x]) swap(x, y);
            data[x] += data[y]; data[y] = x;
        }
        return x != y;
    }
    bool findSet(int x, int y) { return root(x) == root(y); }
    int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
    int size(int x) { return -data[root(x)]; }
};

int main() {
    int N,Q; cin >> N>>Q;
    UnionFind uf(N);
    rep(q,Q){
        int P,A,B; cin >>P>>A>>B;
        switch (P) {
            case 0: uf.unionSet(A,B); break;
            case 1: cout << (uf.findSet(A,B) ? "Yes" : "No") << endl; break;
        }
    }
    return 0;
}

→AC
https://beta.atcoder.jp/contests/atc001/submissions/2582294

C - 高速フーリエ変換

題意は把握。高速に畳み込みたい系の問題。ナイーブに計算したらO(N^2)で、N=100000だし無理ですね。O(NlogN)にしたいのでFFTの出番、です。

と言っても全然わかってないので、問題ページに貼ってあるスライドを読みながら自分で実装してみました。

www.slideshare.net

IDFTは

  • ζ_n^iの代わりにζ_n^{-i}を使うこと(iを-iにするってことは逆回転になるからθを-θにすればいい)
  • 最後に\displaystyle 1/nすること

以外はDFTと全く同じなので同じ関数にフラグを渡して切り替えようと思ったんだけど計算が合わなくて(出てくる数の順番がおかしい)、よくよく見たら再帰する時にフラグを渡してなかった…(そこだけ直したら計算が合うようになった)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

#define rep(var,n)    for(int var=0;var<(n);++var)
#define rep1(var,n)    for(int var=1;var<=(n);++var)

int pow_2_at_least(int n) {
#if 0
    // naive
    int y = 1;
    while (y < n) y <<= 1;
    return y;
#endif
    if (n <= 0) return 0;
    --n;
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    return n + 1;
}

typedef complex<double> Cdbl;

void dft(vector<Cdbl>& f, int n, bool inv=false){ // in-place
    if (n == 1) return;
    int h = n/2;
    vector<Cdbl> f0(h), f1(h);
    for (int i=0; i<h; ++i) {
        f0[i] = f[i*2];
        f1[i] = f[i*2+1];
    }
    dft(f0, h, inv);
    dft(f1, h, inv);
    double th = M_PI * 2 / n;
    if (inv) th = -th;
    Cdbl u(cos(th), sin(th)), ui(1, 0);
    for (int i=0; i<n; ++i) {
        f[i] = f0[i%h] + ui*f1[i%h];
        ui *= u;
    }
}
inline void idft(vector<Cdbl>& f, int n) {
    dft(f, n, true);
    rep(i,n) f[i] /= n;
}

int main() {
    int N; cin >> N; // 1-100000

    int _n = pow_2_at_least(N*2 + 1);
    vector<Cdbl> g(_n, 0), h(_n, 0);

    rep(i,N){
        int A,B; cin >> A >> B;
        g[1+i] = A;
        h[1+i] = B;
    }

    dft(g, _n);
    dft(h, _n);
    vector<Cdbl> f(_n, 0);
    rep(i,_n) f[i] = g[i] * h[i];
    idft(f, _n);

    rep1(k, N*2){
        cout << (ll)round(f[k].real()) << endl;
    }
    return 0;
}

→AC
https://beta.atcoder.jp/contests/atc001/submissions/2583908
行われている計算は概ね理解したのだけれど、(ACは取れたものの)なぜこの実装で十分な精度が出るのかいまいち釈然としない。
答えに出てくる最大の数はN=100000, Ai=Bi=100 for all iの時の10^9(=10^6\cdot10^2\cdot10^2)なので30bitあれば表現できる。floatのmantissaは23ビットなので足りないがdoubleなら52ビットあるから余裕か。
気になるのはそこではなく、複素平面上の回転のほうで、2π/100000(0.0226度)単位の回転というか\sin(ζ_n^i),\cos(ζ_n^i)の誤差が影響しないのかというところ。
(続く?)