12月6日の精進

12月6日

• 解いた問題

diverta 2019 Programming Contest C- AB substrings

diverta 2019 Programming Contest C- AB substrings

problem

解法

int main()
{
    cin >> n ;
    vector<string> S(n);
    ll AB = 0;
    rep(i,n){
        cin >> S[i];
        for(int j = 0 ; j < S[i].size()-1 ; j++){
            if(S[i][j] == 'A' &&S[i][j+1]=='B'){
                AB ++;
            }
        }
    }
    int beginB = 0 , endA = 0 , joker = 0 ; 

    rep(i,n){
        char begin = S[i][0];
        char end = S[i][S[i].size()-1];

        if(begin =='B' && end =='A'){
            joker ++; 
        }
        else if(begin == 'B'){
            beginB++;
        }
        else if(end =='A'){
            endA++;
        }
    }

    
    AB += max(0,joker - 1);
    if(joker>0 &&beginB >= 1){
        AB ++ ;
        beginB --;
    }
    if(joker>0 && endA >= 1){
        AB ++;
        endA --;
    }
    AB += min(beginB,endA);

    cout << AB << endl;
}

Bで終わるものの次にAで終わるものを並べるのが良いです。 しかし、Bで終わりさらにAで終わるものも存在することに気を付けないといけません。

Bで終わりAで始まるものはトランプでいうところのJokerみたいなもんです。

ですのでendA , beginB , joker という変数名を付けました。

で、下でendAはAで終わる文字列、みたいな感じに考えて貰って、並び順は

endA joker joker ... joker beginB と　endA beginB , endA beginB

みたいな感じに並べていくのが良いです。

ここからはendAなどをまた数字としてみてください すると、まずjokerの数-1を答えに足し、(-1の時は0にする） JokerがあってendAもあるなら+1して、jokerがあってbeginBもあるなら+1 そしてendA -- ; beginB -- ; で

endA joker joker ... joker beginB と　endA beginB , endA beginB

これの右側の部分endAとBeginBで作る部分は、その二つの最小値の数だけ文字列動詞の間でABを作り出せます。

連結する前の文字列にABが何個あるかを数えて、それも足すのを忘れないようにしましょう。

終わり