ゆらのふなびと

競プロ, Python, C++

AOJ-ICPC 300 ABC Gene(☆)

問題

ABC Gene | Aizu Online Judge

解法

操作を逆順に考える。ある文字列 t を1段階前の文字列sに戻すことを考えると、t の中にある任意の"ABC"は、sにおいては直前の置換で選んだ文字Xだったはずである。仮にsに"ABC"が含まれていれば、必ずXが"ABC"に置換されるのでsの中の"ABC"がそのまま t に残ることはない。また、Xを置換するという操作以外から"ABC"という文字列は生まれえない。

t に"ABC"以外の形で含まれる文字はXたりえない。先に述べたように、s中のXと t 中の"ABC"が1対1に対応するからである。

以上を踏まえてdfsしたら通った。

gist.github.com