こういうの好き。操作によって実現できるかどうかを問う問題は全体的に好き
問題概要
文字列 "ABC" に対して以下の操作を好きな回数だけ行うことで、所望の文字列 S に変形できるかどうかを判定せよ。
- A, B, C のいずれかの文字を選び、文字列中のその文字をすべて "ABC" に置き換える
制約
操作の特性を考える
操作の性質として一つ言えるのは
操作後の文字列中に含まれる "ABC" はすべて直前の操作によって生じたものである
ということ。もしその "ABC" が直前の操作を行う前の段階で存在していたとしたら、それは
- ABC -> ABCBC
- ABC -> AABCC
- ABC -> ABABC
のいずれかの操作によって上書きされることとなる。ここから言えることは
AABCCABCCABCCABCC
のような文字列があったとき、"ABC" の部分を
A ABC C ABC C ABC C ABC C
というふうに抜き出したとき、これらの ABC は直前の操作前には、すべて同じ文字であったことを意味する。
復元
もう一ついえることは、生成文字列から "ABC" を取り除いたものは、たとえば上の例では
A C C C C
といったように、ABC のうちのちょうど 2 種類で構成されることがいえる。これによって
- 直前の操作が何であったかを完全に復元できる
- 逆にそうでなかったら復元不可能である。
ということになる。
#include <iostream> #include <string> #include <set> using namespace std; bool solve(string S) { if (S == "ABC") return true; bool exist = false; set<char> se; for (int i = 0; i < S.size(); ++i) { if (i + 2 < S.size() && S.substr(i, 3) == "ABC") { i += 2; exist = true; continue; } se.insert(S[i]); } if (se.size() != 2) return false; if (!exist) return false; char c = 'A'; while (se.count(c)) ++c; string nS = ""; for (int i = 0; i < S.size(); ++i) { if (i + 2 < S.size() && S.substr(i, 3) == "ABC") { i += 2; nS += c; continue; } nS += S[i]; } return solve(nS); } int main() { string S; cin >> S; if (solve(S)) cout << "Yes" << endl; else cout << "No" << endl; }