AOJ2708 ABC Gene
問題
方針
まず文字列 $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");
}