DNA Sequence [AtCoder Regular Contest 104 B]

https://atcoder.jp/contests/arc104/tasks/arc104_b

解説

https://atcoder.jp/contests/arc104/submissions/17177217

まず、条件を簡単化できないかを考えてみる。
結論だけ書くと、T1とT2が相補的である条件の言い換えは「AとTが同数、かつ、CとGが同数」である。
なので、区間のATCGの個数を見て条件を満たすかが判定できる。
Nの制約を見ると、区間を全通りしても間に合うので、全探索しよう。

これで5000²通りなので、区間での個数計算はO(1)でやりたい感じがある。
区間を見ていくときに、左端を固定して右端を伸ばしていくような感じで全探索すると思うが、
右端を伸ばすときに個数をカウントしていくと、その区間に含まれる文字の個数がカウントできる。
自分は実装を少しサボってmapを使った。
indexが4つくらいなら、ほぼO(1)感覚で使える。
左端が変更になったときにカウントをリセットするのを忘れないこと。

int N; string S;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> S;
    int ans = 0;
    rep(L, 0, N) {
        map<char, int> cnt;
        rep(R, L, N) {
            cnt[S[R]]++;

            if (cnt['A'] == cnt['T'] && cnt['C'] == cnt['G']) ans++;
        }
    }
    cout << ans << endl;
}