AOJ 1152: 部陪博士,あるいは,われわれはいかにして左右非対称になったか / Dr. Podboq or: How We Became Asymmetric
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;
}