AtCoder Typical Contest #001 に参加しました。

結果

どうも、yoshikyotoです。 AtCoder Typical Contest (http://atc001.contest.atcoder.jp)なるものに参加しました。 結果はこんな感じでした。*1

A - 深さ優先探索

深さ優先探索するだけ。 1度通ったところを2度通らないようにするフラグを用意したりするが、 僕のコードでは通ったところを壁 (#) に変換することで代用している。 また、配列の中に入っているかどうかのチェックはせず、try-catchをすることで済ませている。

• http://atc001.contest.atcoder.jp/submissions/420279

class Main extends MyUtil {
    public static void main(String[] args) throws Exception {
        int h = readIntMap(0);
        int w = readIntMap(1);
        char[][] c = new char[h][];
        for (int i = 0; i < h; i++) {
            c[i] = readLine().toCharArray();
        }
        
        int sh = 0, sw = 0;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if(c[i][j] =='s'){
                    sh = i;
                    sw = j;
                }
            }
        }
        
        if(dfs(sh, sw, c)){
            System.out.println("Yes");
        }else{
            System.out.println("No");
        }
    }
    
    static int[] di = {1, -1, 0, 0};
    static int[] dj = {0, 0, 1, -1}; 
    static boolean dfs(int i, int j, char[][] c){
        for (int k = 0; k < 4; k++) {
            try{
                int ni = i + di[k];
                int nj = j + dj[k];
                if(c[ni][nj] == 'g'){
                    return true;
                }else if(c[ni][nj] == '.'){
                    c[ni][nj] = '#';
                    if(dfs(i+di[k], j+dj[k], c)){
                        return true;
                    }
                }
            }catch(ArrayIndexOutOfBoundsException e){}
        }
        return false;
    }
}

B - Union Find

Union Find Tree を知っているかどうかの問題

• http://atc001.contest.atcoder.jp/submissions/420342

class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(new InputStreamReader(System.in));
        int n = sc.nextInt();
        int q = sc.nextInt();
        
        UnionFindTree uft = new UnionFindTree(n);
        
        for (int i = 0; i < q; i++) {
            int p = sc.nextInt();
            int a = sc.nextInt();
            int b = sc.nextInt();
            
            if(p == 0){
                uft.unite(a, b);
            } else {
                if(uft.same(a, b)){
                    System.out.println("Yes");
                }else{
                    System.out.println("No");
                }
            }
        }
        sc.close();
    }
}
 
/**
 * UnionFindTree 
 * @author yoshikyoto
 */
class UnionFindTree {
    public int[] parent, rank;
    public int n;
    public int count;
 
    // 初期化
    UnionFindTree(int n) {
        this.n = n;
        count = n;
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }
 
    // 根を求める
    int find(int x) {
        if (parent[x] == x) {
            return x;
        } else {
            return parent[x] = find(parent[x]);
        }
    }
 
    // xとyの集合を結合
    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return;
        }
        if (rank[x] < rank[y]) {
            parent[x] = y;
            count--;
        } else {
            parent[y] = x;
            if (rank[x] == rank[y])
                rank[x]++;
            count--;
        }
    }
 
    // xとyが同じ集合か
    boolean same(int x, int y) {
        return find(x) == find(y);
    }
}

C - 高速フーリエ変換

まったく分からなかったが、解説スライド*2を見てなんとなく理解し、実装してみたが通らなかった。あとで復習しなければならない。

通らなかったコード *3 （あと、これだけC++なので注意）

// 高速逆フーリエ変換
const double PI = 4.0*atan(1.0);
const complex<double> I(0,1);
 
void dft(int n, complex<double> a[], 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;
        }
    }
}
 
 
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 = 2;
    while(nn < n + n + 1){
        nn = nn * nn;
    }
    
    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;
        }
    }
    dft(nn, gg, 1);
    dft(nn, hh, 1);
    
    complex<double> *ff = new complex<double>[nn];
    REP(i,nn){
        ff[i] = gg[i] * hh[i];
    }
    dft(nn, ff, -1);
    cout << 0 << endl;
    REP(i, 2*n-1){
        cout << ff[i].real() << endl;
    }
}

参考

• Spaghetti Source - 高速フーリエ変換

*1:レーティングの変動はありません

*2:今回のコンテストは問題と同時に解説も公開されるという特殊なコンテストだった

*3:つまりこのコードは間違っているので注意。