SRM663 Div1 Easy "ABBADiv1"

問題

TopCoder Statistics - Problem Statement

解法

最終的にinitialが反転しないで終わったのか、反転して終わったのかを決め打つ。

■反転しないで終わった時の条件

target = 左側の文字列 + initial + 右側の文字列　とすると、
・左側と右側の文字列で、含まれる'B'の数が一致する事
・左側の文字列の最初が'A'でないこと

■反転して終わった時の条件

target = 左側の文字列 + initial(反転) + 右側の文字列　とすると、
・左側と右側の文字列で、含まれる'B'の数が左側の方が１つ多い事
・左側の文字列の最初が'A'でないこと

事後

ヒントなしで解けたけど、なんか回りくどい方法・・
反対に考えてtarget->initialにできるか？を考えるとよかったポイ

ソースコード

class ABBADiv1 {
    public:
    string canObtain(string initial, string target) {
        int n = initial.size();
        int m = target.size();

        // 順
        for (int i = 0; i <= m - n; i++) {
            bool match = true;
            for (int j = 0; j < n; j++) {
                if (target[i + j] != initial[j]) match = false;
            }
            if (!match) continue;

            int lb = 0;
            for (int j = 0; j < i; j++) {
                if (target[j] == 'B') lb++;
            }
            int rb = 0;
            for (int j = i + n; j < m; j++) {
                if (target[j] == 'B') rb++;
            }
            if (lb != rb) continue;

            if (i != 0 && target[0] == 'A') continue;

            return "Possible";
        }

        // 逆
        reverse(initial.begin(), initial.end());
        for (int i = 0; i <= m - n; i++) {
            bool match = true;
            for (int j = 0; j < n; j++) {
                if (target[i + j] != initial[j]) match = false;
            }
            if (!match) continue;

            int lb = 0;
            for (int j = 0; j < i; j++) {
                if (target[j] == 'B') lb++;
            }
            int rb = 0;
            for (int j = i + n; j < m; j++) {
                if (target[j] == 'B') rb++;
            }
            if (lb != rb + 1) continue;

            if (target[0] == 'A') continue;

            return "Possible";
        }

        // 無理ぃ
        return "Impossible";
    }
};