提出 #75268544

---

ソースコード 拡げる

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
typedef long long ll;
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define FOR(i, a, b) for (int i = (a), i##_len = (b); i <= i##_len; ++i)
#define REV(i, a, b) for (int i = (a); i >= (b); --i)
int main() {
  int n;
  cin >> n;
  string s;
  cin >> s;

  vector<int> sum_a(n+1,0);
  vector<int> sum_b(n+1,0);
  vector<int> sum_c(n+1,0);

  REP(i,n) {
    if (s[i] == 'A')sum_a[i+1] = sum_a[i] + 1;
    else sum_a[i+1] = sum_a[i];

    if (s[i] == 'B')sum_b[i+1] = sum_b[i] + 1;
    else sum_b[i+1] = sum_b[i];

    if (s[i] == 'C')sum_c[i+1] = sum_c[i] + 1;
    else sum_c[i+1] = sum_c[i];
  }

  map<int, int> mp_a_to_b; // a-b
  map<int, int> mp_a_to_c; // a-c
  map<int, int> mp_b_to_c; // b-c
  map<pair<int,int>,int> mp_pair_1; // a-b,a-c
  map<pair<int,int>,int> mp_pair_2; // a-b,b-c
  map<pair<int,int>,int> mp_pair_3; // a-c,b-c
  map<tuple<int,int,int>,int> mp_tuple; // a-b,a-c,b-c

  ll sum = n;
  sum = sum * (n + 1) / 2;

  // 初期値
    mp_a_to_b[0]++;
    mp_a_to_c[0]++;
    mp_b_to_c[0]++;

    mp_pair_1[make_pair(0,0)]++;
    mp_pair_2[make_pair(0,0)]++;
    mp_pair_3[make_pair(0,0)]++;

    mp_tuple[make_tuple(0,0,0)]++;

  REP(i,n){ 
    int a_to_b = sum_a[i+1] - sum_b[i+1];
    int a_to_c = sum_a[i+1] - sum_c[i+1];
    int b_to_c = sum_b[i+1] - sum_c[i+1];

    // A=BまたはB=CまたはA=Cの数
    ll sub = mp_a_to_b[a_to_b] + mp_a_to_c[a_to_c] + mp_b_to_c[b_to_c]
             - mp_pair_1[make_pair(a_to_b,a_to_c)] - mp_pair_2[make_pair(a_to_b,b_to_c)] - mp_pair_3[make_pair(a_to_c,b_to_c)]
             + mp_tuple[make_tuple(a_to_b,a_to_c,b_to_c)];
    
    // printf("%d:%lld\n",i+1,sub);

    sum -= sub;


    mp_a_to_b[a_to_b]++;
    mp_a_to_c[a_to_c]++;
    mp_b_to_c[b_to_c]++;

    mp_pair_1[make_pair(a_to_b,a_to_c)]++;
    mp_pair_2[make_pair(a_to_b,b_to_c)]++;
    mp_pair_3[make_pair(a_to_c,b_to_c)]++;

    mp_tuple[make_tuple(a_to_b,a_to_c,b_to_c)]++;
  }



  cout << sum << endl;
}

提出情報

ジャッジ結果