問題概要

文字列sについて, 以下の置き換え操作ができる。

‘A’ -> “ABC”
‘B’ -> “ABC”
‘C’ -> “ABC”

‘A’, ‘B’, ‘C'のみから構成される文字列S(|S|≦5000)が与えられるので, “ABC"を何回か操作することで文字列Sにできるか判定せよ。

解法1

逆手順を考える。
最後に操作「x -> “ABC"」をして, 文字列Sを作ったとする。（xは'A', ‘B’, ‘C'のどれか)
このとき、Sに含まれる"ABC"は、操作前は「x」になっている必要がある。

証明：(xを含まない文字列) -> “ABC"と変化することはない。また, x -> "ABC"と変化するので、(xを含む文字列) -> "ABC"と変化する ⇒ 変化前の文字列長 = 1が成り立つ。
もちろん, (文字)(文字) -> 「～AB」「C～」といった変化をすることはない。また, “ABC” -> 操作 -> “ABC"と, そのままになることもあり得ない。

よって, 「x -> “ABC"」の逆元は「"ABC” -> x」となる。
（文字列Sに「x -> “ABC"」を適用したあと、「"ABC” -> x」を適用すると、文字列Sが得られる。）

あとは, xを求めればよい。実は、「"ABC"に何回か操作した文字列は必ず、'A'で始まり'C'で終わる」ことから, xは（必要条件で）一意に定まる。

具体的には、以下の場合分けにより, x(の候補)を特定できる。

S = “ABC～"のとき
- “ABC"に何回か操作した文字列は必ず、'A'で始まり'C'で終わる。よって, x = ‘A'である。
S = “～ABC"のとき
- 同様の理由で, x = ‘C'である。
それ以外
- もしx = ‘A'またはx = 'C'のときは, 操作「x -> “ABC"」をしたときに, 先頭または末尾に"ABC"ができてしまう。これは仮定より文字列Sではないので, x = 'B'である。

ここで, 「x = ～である」という文は、正確には「x = ～である必要がある」となる。
すなわち、「"ABC" -> x -> “ABC"」をしたときに、元の文字列が得られることを確かめる必要がある。
(ちなみに, 文字列Sに現れる文字の種類数が2以下の場合は, 解が存在しない。)

あとは頑張るとO(N²)くらいになる。

解法2

「x -> “ABC"」の逆元が「"ABC” -> x」であることを求めてしまえば、あとは適当に逆再生できる。
（文字種が2種類以下⇒No, 「"ABC" -> x -> “ABC"」をしてSが得られる -> 「"ABC” -> x」をSに適用する, を繰り返すだけ）
こちらもO(N²)くらいである。ただし, 計算量の証明には解法1が用いられている。今回はこちらを実装した。

コード

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

//x -> "ABC"
string operate(string s, char x) {
    string t;
    for (int i = 0; i < s.length(); i++) {
        if (s[i] == x) { t += "ABC"; }
        else { t += s[i]; }
    }
    return t;
}

//"ABC" -> x
string inverse(string &s, char x) {
    string t;
    for (int i = 0; i < s.length(); ) {
        if (i + 2 < s.length() && s[i] == 'A' && s[i + 1] == 'B' && s[i + 2] == 'C') {
            t += x;
            i += 3;
        }
        else {
            t += s[i];
            i++;
        }
    }
    return t;
}

//is all char appeared?
bool check(string &s) {
    int cnt[3] = {0};
    for (int i = 0; i < s.length(); i++) {
        cnt[s[i] - 'A']++;
    }
    return (cnt[0] > 0 && cnt[1] > 0 && cnt[2] > 0);
}

int main() {
    string s;
    cin >> s;
    
    while (true) {
        if (!check(s)) { break; }
        if (s == "ABC") { cout << "Yes" << endl; return 0; }
        
        char last = 'z';
        for (char x = 'A'; x <= 'C'; x++) {
            if (operate(inverse(s, x), x) == s) {
                last = x;
                break;
            }
        }
        if (last == 'z') break;
        
        s = inverse(s, last);
    }
    
    cout << "No" << endl;
    return 0;
}

startcpp’s blog

AOJ 2708 ABC Gene

問題概要

解法1

解法2

コード