SRM 663 Div2 Med ABBA

• 復習。本番 TLE しそうだな。と思いながらも愚直な実装で撃墜されたやつ。
• target からは一意に復元ができそうな気はしていたものの、やり方が思いつかなかった。
• 単純に末尾から削っていく逆変換をすればよいだけだった

class ABBA {
public:
string canObtain(string initial, string target) {
        // initial に操作を加えると分岐が増えてしまうので target を initial に
        // なるように逆操作をしてやればよい。
        // target の末尾をけずりつつ必要な逆変換を施す
        while (target.length() > initial.length())
        {
            // 末尾切り出し
            int c = target.back();
            target.erase(target.end()-1);
            // 末尾が B なら変換前のものから反転されていたはず。
            if (c=='B')
                reverse(target.begin(), target.end());
            // 末尾が A ならそのままとりのぞく
        }
        if (target==initial)
            return "Possible";
        else
            return "Impossible";
}
};