Tournament Chart [JAG Practice Contest for ACM-ICPC Asia Regional 2017 B]

https://jag2017autumn.contest.atcoder.jp/tasks/jag2017autumn_b

トーナメントが文字列で与えられる。
「[左-右]」で与えられる。
次にトーナメントに出てきたN人について、勝利回数が分かっている。
勝利回数が正しいかどうか判定せよ。

解法

https://jag2017autumn.contest.atcoder.jp/submissions/1794272

構文解析の問題。
構文解析のよくあるやつが、indexを先頭から動かしていって、再帰で階層を作るやり方がある。
これを順番にやる。
　
あとは、ルートを深い方から順番に合っているか確かめていけばいい。
これは片方は負けるため、残り勝ち回数が0、もう片方は勝つため残り勝ち回数がないとだめ。
これをチェックしていけば答え。

struct Node {
    Node *lef, *rig;
    char c = '?';
};
 
string S;
map<char, int> win;
//---------------------------------------------------------------------------------------------------
int i = 0;
Node* parse() {
    Node *res = new Node();
 
    if (S[i] == '[') {
        i++;
        res->lef = parse();
        assert(S[i] == '-');
        i++;
        res->rig = parse();
        assert(S[i] == ']');
        i++;
    } else {
        char c = S[i]; i++;
        win[c] = 0;
        
        res->c = c;
        res->lef = res->rig = 0;
    }
 
    return res;
}
//---------------------------------------------------------------------------------------------------
string ans = "Yes";
char check(Node* n) {
    if (n->c != '?') return n->c;
 
    char a = check(n->lef);
    char b = check(n->rig);
 
    if (win[a] == 0 and 0 < win[b]) {
        win[b]--;
        return b;
    }
 
    if (win[b] == 0 and 0 < win[a]) {
        win[a]--;
        return a;
    }
 
    ans = "No";
    return a;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S; S += "#";
    auto root = parse();
    int N = win.size();
    rep(i, 0, N) {
        char c; int a;
        cin >> c >> a;
        win[c] = a;
    }
    char c = check(root);
 
    if (win[c] != 0) ans = "No";
    cout << ans << endl;
}