けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ 2708 ABC Gene (JAG 夏合宿 2015 day2C) (300 点)

こういうの好き。操作によって実現できるかどうかを問う問題は全体的に好き

問題へのリンク

問題概要

文字列 "ABC" に対して以下の操作を好きな回数だけ行うことで、所望の文字列 S に変形できるかどうかを判定せよ。

  • A, B, C のいずれかの文字を選び、文字列中のその文字をすべて "ABC" に置き換える

制約

  •  1 \le |S| \le 5000

操作の特性を考える

操作の性質として一つ言えるのは


操作後の文字列中に含まれる "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;
}