TopCoderコミットテスト

TopCoderのネットワーク接続がうまくいかず、様々な方法を試した後、Edgeブラウザ+グローバルエージェントで接続しました.エージェントを使わなくてもいいようです.

Webサイト:https://arena.topcoder.com

ブラシ問題上の欄のPractice Problemをクリックし、テーマをクリックしてページに入るには長い時間ロードする必要があります.Disconnectが表示された後にポイントが続行された場合は、インタフェースで待機し続けます...

問題のロードが完了した後、テストの提出は比較的順調である.Webエディターはカスタムテストをサポートします.

テーマの要求に従って相応の方法を実現する必要がある.

タイトル：ABBA

一つのABからなる文字列が末尾にA、反転後にBを加えて別の文字列に変換できるかどうかを判断する.
一般的にこのような文字列の修正はDPを思い浮かべやすい.しかし、この問題の主な方法は貪欲であるべきだ.まず2文字列のAB個数差を算出し,Bの差から反転回数を判断する.元の文字列が反転した後、前後に続くBの個数とAを追加する位置を決定できます.ターゲット文字列と比較すればよい.

#include 

using namespace std;
typedef long long LL;


class ABBA{
    public:
    string canObtain(string initial, string target){
        int len1 = initial.length();
        int len2 = target.length();
        int cntA = 0, cntB = 0;
        for(char a : initial){
            if(a == 'A'){
                cntA--;
            }
            else{
                cntB--;
            }
        }
        for(char a : target){
            if(a == 'A'){
                cntA++;
            }
            else{
                cntB++;
            }
        }
        if (cntB < 0 || cntA < 0) {
            return "Impossible";
        } else {
            int cntL = cntB / 2;
            int cntR = cntB - cntL;
            bool rev = cntB & 1;
            if (rev) {
                int p = len2 - 1;
                if (!cntR && initial[0] != 'A' && target[0] == 'A') return "Impossible";
                while (cntR) {
                    cntR -= target[p] == 'B';
                    p--;
                }
                if (p - len1 + 1 < 0) return "Impossible";
                for (int i = 0; i < len1; ++i) {
                    int pp = p - i;
                    if (target[pp] != initial[i]) return "Impossible";
                }
                return "Possible";
            }
            else{
                int p = 0;
                if (!cntR && initial[0] != 'A' && target[0] == 'A') return "Impossible";
                while (cntL) {
                    cntL -= target[p] == 'B';
                    p++;
                }
                if (p + len1 > len2) return "Impossible";
                for (int i = 0; i < len1; ++i) {
                    int pp = p + i;
                    if (target[pp] != initial[i]) return "Impossible";
                }
                return "Possible";
            }
        }

    }
};