AOJ 2708 - ABC Gene
解法
この問題は、初期状態であるABCから2手分ぐらいを書き出し、あとは後ろから見ていくということに気づくと、うまく解くことができます。
後ろから見ていったとき、ABCと綺麗に並んでいる部分は、かならず1手前で1文字を置換した結果できたものになります。ので、後ろから戻していくときに、ABCと並んでいる文字列をすべてなんかしらの1文字に置き換えていけばいいのですが、置き換えるべき文字もすでに決まっています。
ABCで置き換える部分以外は、必ず2種類の文字でないといけないため、それ以外の1文字が置換するべき文字になります。
具体例で説明すると、"ABCABCBCBC"という文字列が存在したとき、
ABCABCBCBCBCというようにABCという文字列が2つ存在するので、そこを置換すると1つ前の状態に戻れるのですが、この際に置換するべき文字は、他のBCBCBCの部分に含まれていない、'A'になります。
ということで、1つ前の状態は"AABCBC"となります。
さて、ABCから派生できるかどうかの判定をする問題なので、判定条件が必要になります。
これは、単純に戻すことができるかどうかなので、ABCという文字列以外の文字が、1種類以下、もしくは3種類存在した場合になります。
たとえば"AABCBC"だと、AABCBCとなり、A、B、Cすべての文字が存在しているため、この1つ手前の状態に戻すことができないため、答えがNoとなります。
あとは、文字列が最初のABCとなるまで、この作業を繰り返すことができれば答えはYesとなります。
