AOJ2708 ABC Gene

2016/07/30 (Sat) AOJ 貪欲

問題

問題文

方針

まず文字列 $S$ から以下の置換えを繰り返して ABC に戻せるか判定する。

  • 現在の $S$ が ABC で始まるなら ABC -> A
  • 現在の $S$ が ABC で終わるなら ABC -> C
  • そうでないなら B -> ABC

次に、手順を逆から ABC に対して行って $S$ に戻せるか判定する。

実装

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

void replace(string &s, char c) {
    for (size_t p = s.find("ABC"); p != string::npos; p = s.find("ABC", p + 2)) {
        s[p] = c;
        s[p + 1] = s[p + 2] = '@';
    }
    s.erase(remove(s.begin(), s.end(), '@'), s.end());
}

bool solve(string s) {
    string t = s;
    string log;
    const string abc = "ABC";
    while (t != abc && t.find(abc) != string::npos) {
        if (t.substr(0, 3) == abc) {
            replace(t, 'A');
            log += 'A';
        } else if (t.substr(t.size() - 3, 3) == abc) {
            replace(t, 'C');
            log += 'C';
        } else {
            replace(t, 'B');
            log += 'B';
        }
    }
    if (t != abc) return false;
    reverse(log.begin(), log.end());
    for (int i = 0; i < log.size(); i++) {
        for (int j = 0; j < t.size(); j++) {
            if (t[j] == log[i]) {
                t.erase(t.begin() + j);
                t.insert(t.begin() + j, abc.begin(), abc.end());
                j += 2;
            }
        }
    }
    return s == t;
}

int main() {
    string s;
    cin >> s;
    puts(solve(s) ? "Yes" : "No");
}