Algoogle

Algorithm for Programming Contest

Codeforces 451D Count Good Substrings

Category: Codeforces Tag: dp

Count Good Substrings

問題概要


a, bからなる文字列の部分文字列について, 隣り合う同じ文字をすべて1つにまとめた文字列が回文になるもののうち長さが奇数のものと偶数のものはそれぞれいくつあるか

解法


一番左と右の文字が同じになれば回文になる.
長さが偶数の場合は, 両端の文字の位置の偶奇が異なり,
長さが奇数の場合は, 両端の文字の位置の偶奇が等しい.
よって各位置までのa, bそれぞれが偶数番目と奇数番目に何個現れるかを数えておく.
そうすると左端を固定した時, そこから最後までに左端の文字と同じ文字が場所の偶奇ごとに現れる回数がO(1)で求まるので, 左端を順に見てやればよい.

コード


(451D.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <bits/stdc++.h>
using namespace std;
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i,a) repi(i,0,a)
typedef long long ll;
string s;
ll ans[2], sum[100010][2][2], t[100010], n;

void solve(){
    n = s.size();
    rep(i,n){
        t[i] = s[i]-'a';
        memcpy(sum[i+1],sum[i],sizeof(sum[i]));
        ++sum[i+1][t[i]][i%2];
    }
    rep(i,n)rep(j,2) ans[j] += sum[n][t[i]][(i+j+1)%2]-sum[i][t[i]][(i+j+1)%2];
    cout << ans[0] << " " << ans[1] << endl;
}

int main(){
    cin.sync_with_stdio(0);
    cin >> s;
    solve();
    return 0;
}

Comments