AOJ 1152: 部陪博士,あるいは,われわれはいかにして左右非対称になったか / Dr. Podboq or: How We Became Asymmetric

,

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1152

solution

問題文を頑張って読んでその通りに実装する。文字列の長さ$N \le 400$くらいに対して$O(N^3)$ぐらい。

以下注意点:

  • struct tree_t { tree_t *l, *r; }のようにするだろうが、一致判定や全順序を入れるのは文字列に戻してからすると楽
  • 問題文中の「構造」とは、単に根付き木としての同型性だけを見ており、子の左右の別はない
  • $-1, 0, +1$を返すはずの関数cmpの戻り値の型をboolにしてWAした

implementation

#include <cassert>
#include <functional>
#include <iostream>
#include <memory>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
using ll = long long;
using namespace std;

struct tree_t {
    shared_ptr<tree_t> l, r;
};

shared_ptr<tree_t> parse_tree(string::const_iterator & first, string::const_iterator last) {
    assert (first != last);
    if (*first == 'x') {
        ++ first;
        return shared_ptr<tree_t>();
    } else {
        assert (*first == '(');
        ++ first;
        auto l = parse_tree(first, last);
        assert (*first == ' ');
        ++ first;
        auto r = parse_tree(first, last);
        assert (*first == ')');
        ++ first;
        return make_shared<tree_t>((tree_t) { l, r });
    }
}
shared_ptr<tree_t> parse_tree(string const & s) {
    auto it = s.begin();
    auto tree = parse_tree(it, s.end());
    assert (it == s.end());
    return tree;
}

struct rational {
    int num, den;
};
bool operator < (rational a, rational b) {
    return a.num *(ll) b.den < b.num *(ll) a.den;
}
bool operator > (rational a, rational b) {
    return a.num *(ll) b.den > b.num *(ll) a.den;
}

string signature(shared_ptr<tree_t> const & tree) {
    if (not tree) {
        return "x";
    } else {
        string l = signature(tree->l);
        string r = signature(tree->r);
        if (l > r) swap(l, r);
        return "(" + l + " " + r + ")";
    }
}

void normalize(shared_ptr<tree_t> root) {
    unordered_map<string, unordered_set<string> > subtrees; {
        function<void (shared_ptr<tree_t> const &)> go = [&](shared_ptr<tree_t> const & tree) {
            subtrees[signature(tree)].insert(signature(tree));
            if (tree) {
                go(tree->l);
                go(tree->r);
                for (auto it : subtrees[signature(tree->l)]) {
                    subtrees[signature(tree)].insert(it);
                }
                for (auto it : subtrees[signature(tree->r)]) {
                    subtrees[signature(tree)].insert(it);
                }
            }
        };
        go(root);
    }
    unordered_map<string, rational> sim; {
        function<void (shared_ptr<tree_t> const &)> go = [&](shared_ptr<tree_t> const & tree) {
            if (not tree) {
                sim[signature(tree)] = (rational) { 0, 1 };
            } else {
                auto l = subtrees[signature(tree->l)];
                auto r = subtrees[signature(tree->r)];
                int num = 0;
                for (auto it : l) {
                    num += r.count(it);
                }
                int den = l.size() + r.size() - num;
                sim[signature(tree)] = (rational) { num, den };
                go(tree->l);
                go(tree->r);
            }
        };
        go(root);
    }
    const int LT = -1;
    const int EQ =  0;
    const int GT = +1;
    function<int (shared_ptr<tree_t> const &, shared_ptr<tree_t> const &)> cmp = [&](shared_ptr<tree_t> const & a, shared_ptr<tree_t> const & b) {
            rational sim_a = sim[signature(a)];
            rational sim_b = sim[signature(b)];
            // 1.
            if (sim_a < sim_b) return GT;
            if (sim_a > sim_b) return LT;
            // 2.
            if (not a and not b) return EQ;
            // 3.
            auto al = a->l, ar = a->r;
            auto bl = b->l, br = b->r;
            if (cmp(al, ar) == GT) swap(al, ar);
            if (cmp(bl, br) == GT) swap(bl, br);
            int cmp_ar_br = cmp(ar, br);
            if (cmp_ar_br != EQ) return cmp_ar_br;
            // 4.
            int cmp_al_bl = cmp(al, bl);
            if (cmp_al_bl != EQ) return cmp_al_bl;
            // 5.
            return EQ;
    };
    function<void (shared_ptr<tree_t>, bool)> go = [&](shared_ptr<tree_t> tree, bool is_right) {
        if (not tree) {
            // nop
        } else {
            if (cmp(tree->l, tree->r) == (is_right ? GT : LT)) {
                swap(tree->l, tree->r);
            }
            go(tree->l, false);
            go(tree->r, true);
        }
    };
    go(root, false);
}

string format_tree(shared_ptr<tree_t> const & tree) {
    if (not tree) {
        return "x";
    } else {
        return "(" + format_tree(tree->l) + " " + format_tree(tree->r) + ")";
    }
}

int main() {
    while (true) {
        string s; getline(cin, s);
        if (s == "0") break;
        auto tree = parse_tree(s);
        normalize(tree);
        cout << format_tree(tree) << endl;
    }
    return 0;
}