AtCoder Typical Contest 001 をD言語で解いた（A, B問題）

競プロ界隈重要アルゴリズムが大会形式でchokudaiさんのスライドを見ながら提出できるという神コンテストが開催されたので，勉強不足な僕も参加してみました．RubyでDFSを書き始めたらデバッグが全く進まなくて無事死亡したので後日D言語で改めて解いたものをブログに残しておきます．

A問題

迷路をスタートからゴールまで行く．深さ優先探索という問題なので一応それで．迷路と言われたら普通最短解で幅優先な気がするけどTwitter見てたらUnion Findでも解けるみたいな意見を見て「？？？？？？」ってなってた．やり方が全く思いつかない．

import std.stdio;
import std.range;
import std.string;

void main() {
    int H, W;
    readf("%d %d\n", &H, &W);

    string[] c;
    int[] s = new int[2];
    foreach (int i, string line; stdin.lines) {
        c ~= line.chomp;
        foreach (int j, ch; line) {
            if (ch == 's')
                s = [ i, j ];
        }
    }

    /**
     * ある地点に訪問済みかどうかを記録しておく配列
     * 記録しておかないと同じ地点を永遠にさまよい続ける
     */
    bool[][] visit = new bool[][](H, W);

    if (dfs(H, W, s[0], s[1], c, visit))
        writeln("Yes");
    else
        writeln("No");
}

/**
 * 深さ優先探索で迷路を探索する
 * H: 高さ, W: 幅, h: 今いる場所の縦位置, w: 今いる場所の横位置
 * c: 迷路 v: 記録シート
 */
bool dfs(int H, int W, int h, int w, string[] c, bool[][] v) {
    // 迷路からはみ出たらやめる
    // これを一番最初に弾いとかないと Range violation で実行時に落ちる
    if (h < 0 || H <= h || w < 0 || W <= w)
        return false;

    // 訪問済みだったらやめる
    if (v[h][w])
        return false;

    // 壁だったらやめる
    if (c[h][w] == '#')
        return false;

    // ゴールに辿り着いたら成功
    if (c[h][w] == 'g')
        return true;

    // 今たどり着いたマスをチェックしておく
    v[h][w] = true;

    // 上下左右のうちどれかがゴール = trueだったらいいので論理和を返す
    return dfs(H, W, h - 1, w, c, v) ||
        dfs(H, W, h + 1, w, c, v) ||
        dfs(H, W, h, w - 1, c, v) ||
        dfs(H, W, h, w + 1, c, v);
}

readf で改行を読み込み忘れたり，配列のサイズをコンパイル時に確保しといたのに実行時に ~= で追加して前の方に空白の要素が出来ちゃったりいろいろな凡ミスをしてしまった．いい加減流れを覚えたい．あと最初はスタックを使って書いてみたけど配列を適当に弄ったのでたぶんスタック配列からの取り出しとか追加に時間がかかってTLEで落ちた．関数の再帰呼出しに書き直したら普通に通った．でもスタックオーバーフローで落ちるのこわい．

B問題

N個ある要素をつなげたり，与えられた2つの要素が繋がっているかどうかの判定をしたりしたい．Union Findって今まで名前は知ってたけどどういうものか分からなかったので，今回のお陰で理論と実装が分かってよかった．応用の仕方は全く分からないので良い問題を教えてほしい．

import std.stdio;
import std.range;

void main() {
    int N, Q;
    readf("%d %d\n", &N, &Q);

    int[] uf = new int[](N);
    // 最初は各要素が自分を見るようにする
    // ref を付けないとコピーしたのを見てしまうので意味が無い
    foreach (int i, ref e; uf) {
        e = i;
    }

    foreach (q; iota(0, Q, 1)) {
        int p, a, b;
        readf("%d %d %d\n", &p, &a, &b);

        if (p == 0) {
            unite(a, b, uf);
        } else {
            if (find(a, b, uf))
                writeln("Yes");
            else
                writeln("No");
        }
    }
}

bool find(int a, int b, int[] uf) {
    return (root(a, uf) == root(b, uf));
}

// 引数で受け取ったUF木を直接いじりたいのでrefを付ける
void unite(int a, int b, ref int[] uf) {
    int x = root(a, uf);
    int y = root(b, uf);

    // もし根が違ったら根どうしを繋げる
    if (x != y)
        uf[x] = y;
}

int root(int x, int[] uf) {
    // 自分自身を参照しているところが根
    if (uf[x] == x)
        return x;
    else
        // 代入しながら再帰することで，途中経過で参照したノードを全て
        // 根に繋げることができる
        // 例：uf[2] = uf[5] = uf[3] = uf[4] = 4
        //     で，2と5と3がこれ以降直接4を見てくれるようになる
        return uf[x] = root(uf[x], uf);
}

C問題は脳が途中で理解しようとする努力をやめてしまいました．南無三．