Submission #75259765

---

Source Code Expand

#line 2 "/Users/blue_jam/ProconLibrary/misc/template.hpp"

#include <atcoder/all>
#include <bits/stdc++.h>

using namespace std;
using namespace atcoder;

#define ALL(x) (x).begin(), (x).end()

using ll = long long;
#ifndef EPS
const double eps = 1e-10;
#else
const double eps = EPS;
#endif
#line 2 "abc455/E/main.cpp"


void solve(long long N, std::string S) {
    for (ll i = 0; i < N; i++) {
        S[i] -= 'A';
    }
    ll t[3][3];
    map<ll, vector<ll>> mp[3][3];
    map<pair<ll,ll>, ll> mp2;
    for (ll i = 0; i < 3; i++) {
        for (ll j = i + 1; j < 3; j++) {
            t[i][j] = 0;
            mp[i][j][0].push_back(0);
        }
    }
    mp2[{0, 0}]++;
    for (ll i = 0; i < N; i++) {
        for (ll j = 0; j < 3; j++) {
            for (ll k = j + 1; k < 3; k++) {
                if (S[i] == j) {
                    t[j][k]++;
                } else if (S[i] == k) {
                    t[j][k]--;
                }
                mp[j][k][t[j][k]].push_back(i + 1);
            }
        }
        mp2[{t[0][1], t[1][2]}]++;
    }
    ll ans = 0;
    for (ll i = 0; i < 3; i++) {
        for (ll j = i + 1; j < 3; j++) {
            for (auto &&[t, v] : mp[i][j]) {
                ll n = v.size();
                ans += n * (n - 1) / 2;
            }
        }
    }
    for (auto [p, n] : mp2) {
        // cerr << p.first << "," << p.second << ":" << n << endl;
        ans -= n * (n - 1);
    }
    cout << N * (N + 1) / 2 - ans << endl;
}

int main() {
    long long N;
    std::scanf("%lld", &N);
    std::string S;
    std::cin >> S;
    solve(N, S);
    return 0;
}

Submission Info

Judge Result