SRM 658 div1 easy:OddEvenTree

SRM 658に参加しました。結果はeasyを200ptくらいで通してそこそこでした。そろそろmedも通してみたいですね…

問題

解法

まず木が存在するかどうかを考える。以下の条件が成り立っていることが,条件を満たす木が存在する条件である。

・x[i][i] = 'E'となること
・x[i][j] = x[j][i]となること
・頂点が2つ以上ある場合,すべての頂点が'E'になっていないこと(距離1の頂点は必ず1つは存在しないとおかしい)
・x[i][j] = x[i][k]ならば,x[j][k] = 'E'となること(理由はあとで)
・x[i][j] != x[i][k]ならば,x[j][k] = 'O'となること(理由はあとで)

後半2つの理由を説明する。
木の頂点j, kについて,jからkにたどり着くためには,

・iを経由する
・iを経由しない

の2通りがあるが,

・iを経由する場合は,x[i][j] とx[i][k]の経路の長さがどちらも偶数だったり奇数だったりしたら,偶数+偶数も奇数+奇数も偶数なのでx[j][k]は偶数になる。

・iを経由しない場合は,i以外にjとkのlowest common ancestorである頂点lがあるはずである。iからlへの距離は決まっているので,結局x[i][j]とx[i][k]がどちらも偶数か奇数だったらx[l][j]とx[l][k]も同じ偶奇になるのでx[j][k]は偶数になる。

これで-1を返す場合はすべて網羅してそう(はっきりした証明はできないので誰か教えてください)。あとは構成できる場合について,どうやって木を作ればよいのかを考えればよいが,これは簡単にできて,x[0][i]が奇数だったら0から直接iにつなげてx[0][i]が偶数だったら0から直接つなげた頂点jについてjとiをつなげれば良い。このようにすると,上の条件はすべて満たせる。

以下ソースコード。これでは-1を返す場合の後半2つについて,0からの距離しかやってなくて,少々危ない。

class OddEvenTree {
public:
    vector <int> getTree(vector <string> x) {
        int n = x.size();
        vector<int> ret;
        for (int i = 0; i < n; i++) {
            if (x[i][i] == 'O') {
                ret.push_back(-1);
                return ret;
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (x[i][j] != x[j][i]) {
                    ret.push_back(-1);
                    return ret;
                }
            }
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < n; j++) {
                int di, dj, dist;
                if (x[0][i] == 'O') di = 1;
                else di = 0;
                if (x[0][j] == 'O') dj = 1;
                else dj = 0;
                dist = (di+dj) % 2;
                if (dist == 0) {
                    if (x[i][j] == 'O') {
                        ret.push_back(-1);
                        return ret;
                    }
                } else {
                    if (x[i][j] == 'E') {
                        ret.push_back(-1);
                        return ret;
                    }
                }
            }
        }
        vector<vector<int> > T(n);
        for (int i = 1; i < n; i++) {
            if (x[0][i] == 'O') {
                T[0].push_back(i);
            }
        }
        for (int i = 1; i < n; i++) {
            if (x[0][i] == 'E') {
                if (T[0].size() == 0) {
                    ret.push_back(-1);
                    return ret;
                }
                T[T[0][0]].push_back(i);
            }
        }
        for (int i = 0; i < n; i++) {
            for (int el : T[i]) {
                ret.push_back(i);
                ret.push_back(el);
            }
        }
        return ret;
    }
};

mayoko’s diary

プロコンとかいろいろ。

SRM 658 div1 easy:OddEvenTree

問題

解法