AGC019 B : Reverse and Compare(500)
作成日：2017.08.30
最終更新日：2017.08.30
問題概要
英小文字からなる文字列$A$がある。
$A$の$i$文字目から$j$文字目までを反転させる操作を一回まで行う時に得られる文字列で異なるものは何通りあるかを求めよ。
制約
$1 \leq |A| \leq 2 \times 10^5$
考え方
元の文字列と操作後の文字列が同じになる条件は、明らかに操作時に選ばれた区間が回文になっていることである。
以下、回文でない異なる区間に対して操作を行った時に文字列が一致する条件を考える。
操作後の文字列が一致する時、操作を行った区間の共通していない部分は不変である必要があるから、共通している部分を1文字と考えた時に選ばれた区間は回文になっている必要がある。
特に共通していない部分が存在すれば区間の始めと終わりの文字は一致する。
逆に区間の始めと終わりの文字が一致している時、それらを取り除いた区間と元の区間に対してそれぞれ操作を行った時には文字列は一致する。
このことは2文字以上の回文に対しても当てはまるから、答えは2文字以上の区間の数から始めと終わりの文字が同じである区間の数を引いたものに元の文字列分の$1$を加えたものになる。
ソースコード
マクロ等はこちら
const int MC = 200010;
char A[MC];
int c[26];
int main(){
scanf("%s" , A);
int n = 0;
for(; A[n] != 0 ; ++n){
++c[A[n]-'a'];
}
LL ans = (LL)n * (n-1) / 2 + 1;
repp(i,0,26) ans -= (LL)c[i] * (c[i]-1) / 2;
printf("%lld\n" , ans);
return 0;
}解法まとめ
2文字以上の区間の数に$1$を加えたものから始めと終わりの文字が同じである区間の数を引いたものを求める。(8-12行)