AOJ 2708 ABC Gene
問題概要
文字列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(N2)くらいになる。
解法2
「x -> “ABC"」の逆元が「"ABC” -> x」であることを求めてしまえば、あとは適当に逆再生できる。
(文字種が2種類以下⇒No, 「"ABC" -> x -> “ABC"」をしてSが得られる -> 「"ABC” -> x」をSに適用する, を繰り返すだけ)
こちらもO(N2)くらいである。ただし, 計算量の証明には解法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; }