diverta 2019 Programing Contest C-AB Substrings

今日はこの問題の僕の実装を書きたいと思います。

問題の概略は、与えられるいくつかの文字列すべてをうまくつなげてそのなかに"AB"という部分文字列が最大でいくつ作ることができるかという問題です。

コンテスト中の思考

まず大雑把に問題を把握し、考えたこととして、とりあえずそれぞれの文字列に"AB"がいくつあるか考えて、後は端の処理が必要かなという感じです。ここでそれぞれの文字列で最初がB最後がAならそれらをくっつければ"AB"ができるよねと思い、それは何個できるのか考えているとわりとすぐに最初がBの文字列の個数と最後がAの個数の小さい方分だけ"AB"ができるよねと思いました。具体的にはこんな感じです。

BCD

BFS

XYZA

こんな例ですと、

BCD XYZA BFS

みたいにつなげば良いですね。要は端同士をつなげるのだから小さい方分だけ"AB"ができるよね。という感じです。これをパッと実装し投げたところ普通に落ちました()。そこで色々コーナーケースのようなものを考えているとB~Aみたいな文字列が出てきた場合処理に戸惑うなと考えました。簡単な例を出すと、

BCA

BDA

BEA

みたいな感じです。これでは最初のように考えると答えはmin(3,3)=3となりますが正しくは

BCA BDA BEA

とつないでも答えは最大で2にしかなりません。つまりこのような場合を別に考えなければいけないと思いました。ここから無限に時間を使い色々考えた結果以下のように場合分けすると個人的にはスッキリしました。

B~X,Y~Aみたいな文字列をそれぞれカウント
B~Aみたいな文字列をカウント

この下で

1.B~Aがない時、先ほどの説明通りが答え
2.B〜Aしかない時、先ほどの説明通りの答え-1になる
3.B〜AもB~XもA~Yもある時(B~X,Y~Aはどちらも0を除く) それぞれの文字列内にある"AB"の数+(B~Aの数+B~X,Y~Aの小さい方の数)

3の場合がわかりにくいかもしれません。具体例を考えます。

BDA

BEFA

BGA

BSX

YTA

YUA

これのつなげかたは

YTA BDA BEFA BGA BSX YUA で4が答えです。実際にcase.3に当てはまっていることを確かめてください。これを以下のように実装しました。適宜コメントアウトしています。

#include <iostream>
#include<vector>

using namespace std;



#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

int main() {
int n;
vector<string> s(n);
cin >> n;
for (int i = 0; i < n; i++) cin >> s[i];
int cnt = 0;
//まずはそれぞれの文字列にABが何個あるか数える
for (int i = 0; i < n; i++){
    for (int j = 0; j < s[i].size()-1; j++)
    {
        if(s[i][j]=='A' && s[i][j+1]=='B') cnt++;
        }
 
}
//一番左にBが何個あって一番右にAが何個あるか調べる
//このときB〜Aみたいな文字とB~X、Y〜Aみたいな文字列を区別する
int left_B=0,right_A=0;
int x=0;
for(int i=0;i<n;i++){
    int last = s[i].size() - 1;
    if (s[i][0] == 'B' && s[i][last] != 'A')
        left_B++;
    if (s[i][last] == 'A' && s[i][0] != 'B')
        right_A++;
    if (s[i][0] == 'B' && s[i][last] == 'A')
        x++;
}
//B~AがなかったらBの数かAの数の小さい方が答え(文字列をくっつけていくイメージ)
if(x==0) cout<< cnt+min(left_B,right_A)<<endl;

//もし文字列がB〜Aの形だけなら合計から１日引く必要がある(端同士は繋げられない)
else if(left_B==0 && right_A==0 && x>=1) cout<<cnt+x-1<<endl;

//それ以外ではB~A部分の数+B~XとY~Aの小さい方の和を考えれば良い
else cout<<cnt+x+min(left_B,right_A)<<endl;

    return 0;
}