文字列操作(AGC019B - Reverse and Compare)

atcoder.jp

綺麗に思いついたし時間もそこまでかからなかった。実装が簡単だったのでよかった
やっぱり計算量が大きい解法をまず考えて縮めていくのがよいっぽい。

考え方の途中経過

あるi,jを選んだ操作によって、場所が入れ替わる(int)(j-i+1)/2ペアについて、
(i-k,j+k)について同じ操作を行ってもそこは同じように入れ替わる。その操作と(i,j)の操作で違う文字列が生まれるかどうかは、i-k~i-1,j+1~j+kの位置の文字による。
よって、中心とする場所（任意の文字か文字同士の間）それぞれについて、どんどんi--j++した範囲を調べていけば、そこを中心とした操作により生まれる違った文字列の数（これは他のところを中心にした時と重複がない）が求められる。場所は2|A|+1,範囲は|A|/2あるので、まだ計算量が多い。

解法

逆に考えれば、同じ文字の組み合わせがある時、その二つを端とする入れ替えの選択はその二つの端を除いた区間の入れ替えを行った時の結果と同じになるので、1(そのままの文字列)+(全ての同じでないi,jの選び方の数)-(同じ文字の組み合わせの数)で求める場合の数がわかる。文字列の長さをNとすると、

• 全てのi,jの選び方はN_C_2
• 同じ文字の組み合わせの数は、26文字に対してそれぞれの個数をKとするとK_C_2 を計算してたしていけばいい。

計算量は文字列を調べる時のNだけでよい。

コード

#include<cstdio>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<set>
#include<cstring>
 
 
using namespace std;
#define int long long int
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1001001001
#define LLINF 1001001001001001001
#define mp make_pair
#define pb push_back


char A[200005];
int ans=0;
int cnt[30];
signed main(){
    
    scanf("%s",A);
    int N=strlen(A);
    ans+= 1+(N*(N-1)/2 );
    rep(i,N){
        cnt[A[i]-'a']++;
    }
    rep(i,26){
        int K=cnt[i];
        ans-=K*(K-1)/2;
    }
    printf("%lld\n",ans);
}