JAG Contest 2016 Domestic C - みさわさんの根付き木
JAG Contest 2016 Domestic に参加しました。チーム戦楽しいですね。もう全部チームで参加したい。
解法
愚直にやりました。
- A, B の文字列から木を構成(dfs)
- 2 つの木の情報から目的の木を構成(dfs2)
- 目的の木を出力(dfs3)
dfs2, dfs3 は簡単なので置いておきます。dfs は構文解析ゲーですが,
各 dfs において,
- 左の子を調べる
- 今のノードの数字を求める
- 右の子を調べる
とやれば良いです(そんなことみんなわかってそうですが)。
実装めっちゃ苦労して, チームの人と相談しながらやってたんですが, やっぱり不変条件を意識するのが大事だと思います。今回の場合,
- dfs に入るときは必ず ptr は '(' に入る
- dfs を出るときは必ず ptr は ')' から一つ進むところにいる
を意識する(というかそういう条件が成り立つように書く)と考えやすいです。
struct Node { Node* left; Node* right; int num; Node() : left(0), right(0), num(-1) {} }; int value(const string& s, int& ptr) { int ret = 0; while ('0' <= s[ptr] && s[ptr] <= '9') ret = ret*10+(s[ptr++]-'0'); return ret; } void dfs(Node* node, const string& s, int& ptr) { //cout << ptr << endl; assert(s[ptr] == '('); // まず左 if (s[ptr+1] == ')') { ptr++; } else { node->left = new Node(); dfs(node->left, s, ++ptr); } assert(s[ptr] == ')'); ptr++; assert(s[ptr] == '['); // 値 node->num = value(s, ++ptr); assert(s[ptr] == ']'); ptr++; // 右 if (s[ptr+1] == ')') { ptr++; } else { node->right = new Node(); dfs(node->right, s, ++ptr); } ptr++; } void dfs2(Node* nodeA, Node* nodeB, Node* node) { node->num = nodeA->num+nodeB->num; if (nodeA->left != NULL && nodeB->left != NULL) { node->left = new Node(); dfs2(nodeA->left, nodeB->left, node->left); } if (nodeA->right != NULL && nodeB->right != NULL) { node->right = new Node(); dfs2(nodeA->right, nodeB->right, node->right); } } void dfs3(Node* node) { if (node->left == NULL) cout << "()"; else { cout << "("; dfs3(node->left); cout << ")"; } cout << "[" << node->num << "]" ; if (node->right == NULL) cout << "()"; else { cout << "("; dfs3(node->right); cout << ")"; } } int main() { string A, B; cin >> A >> B; Node* rootA = new Node(); Node* rootB = new Node(); int cur = 0; dfs(rootA, A, cur); cur = 0; dfs(rootB, B, cur); Node* root = new Node(); dfs2(rootA, rootB, root); dfs3(root); cout << endl; return 0; }