Educational Codeforces Round 74 D. AB-string (R1800)

面白かった

問題へのリンク

問題概要

文字列 が good であるとは、 の連続部分文字列であって回文であるような区間をすべてとってきたときに、それらによって が被覆されることをいう。たとえば "aaba" は、"aa" と "aba" によって被覆されるので good である。

長さ の文字列 が与えられる。 の連続部分文字列であって good なものが何個あるかを数えよ。

制約

• 

考えたこと

最初 good の条件を「被覆される」ではなく「分割される」と誤読して迷走した。

さて、good な条件がとてもわかりづらいので、これをわかりやすく特徴付けよう。まず思うことは、"A" と "B" との変わり目が 2 箇所以上あったら問答無用で good になる。

• AAABAA とかは、"AAA" が good で、"ABA" が good で "AA" が good

という具合だ。なので good でないものを特徴づけた方が早そうだ。少し考えると、good でない文字列は

• AA...AB
• BB...BA
• ABB...B
• BAA...A

の形に絞られることがわかった。ここまでわかれば、与えられた文字列 の部分文字列であって、good でないものは明快に数えられる。

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

long long N;
string S;

long long solve() {
    long long res = N * (N+1) / 2 - N;
    vector<long long> num;
    for (int i = 0; i < N; ) {
        int j = i;
        while (j < N && S[j] == S[i]) ++j;
        num.push_back(j - i);
        i = j;
    }
    int M = num.size();
    for (int i = 0; i+1 < M; ++i) {
        res -= num[i] + num[i+1] - 1;
    }
    return res;
}

int main() {
    while (cin >> N >> S) {
        cout << solve() << endl;
    }
}