読者です 読者をやめる 読者になる 読者になる

mayoko’s diary

プロコンとかいろいろ。

JAG Contest 2016 Domestic C - みさわさんの根付き木

AtCoder

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;
}