結果

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

f:id:yoshiki_utakata:20150606233944p:plain

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;
    }
}