Japan Alumni Group Summer Camp 2015 Day 2 C - ABC Gene

問題

jag2015summer-day2.contest.atcoder.jp

解法

逆からたどっていく感じでやります。

"ABC" という文字列を見つけたら, それを "A" "B" "C" のいずれかに変換する, ということを繰り返して, 最終的な文字列が "ABC" になったら勝ちです。ただし, 例えば "ABC" を "A" に変換する場合, 文字列に "ABC" というセット以外で "A" という文字列があってはいけません(そうすると, その "A" も "ABC" に変換しなければならないから)。

bool dfs(const string& s) {
    if (s == "ABC") return true;
    vector<int> a;
    int n = s.size();
    for (int i = 0; i < 3; i++) {
        string t;
        bool ng = false;
        for (int j = 0; j < n; ) {
            if (s.substr(j, 3) == "ABC") {
                t += (char)('A'+i);
                j += 3;
            } else if (s[j] == (char)('A'+i)) {
                ng = true;
                break;
            } else {
                t += s[j++];
            }
        }
        if (ng) continue;
        if (t.size() >= s.size()) continue;
        if (dfs(t)) return true;
    }
    return false;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    if (dfs(s)) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}