AGC019 B - Reverse and Compare
やり直し B: Reverse and Compare - AtCoder Grand Contest 019 | AtCoder
問題概要
- 英小文字からなる文字列A(|A|≦200,000)が与えられる
- Aの英小文字2つを選んでそれを両端とする文字列を反転させることを1回まで行う
- 何通りの文字列ができるか
解法
A = abcdbの時
両端の組み合わせは5C2あるが、
bcdb を反転させた文字列と cd を反転させた文字列は同じである。
両端が同じ英小文字を選ぶ場合は重複してカウントしてしまうので5C2から1引く必要がある。
aが何個あるか、bが何個あるか、cが...zが何個あるか数えて重複する部分を引けば良い。
コード
#include <algorithm> #include <cstdio> #include <iostream> #include <map> #include <cmath> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <vector> #include <stdlib.h> #include <stdio.h> #include <bitset> #include <cstring> using namespace std; #define FOR(I,A,B) for(int I = (A); I < (B); ++I) #define CLR(mat) memset(mat, 0, sizeof(mat)) typedef long long ll; int main() { ios::sync_with_stdio(false); cin.tie(0); string A; cin >> A; ll len = A.length(); ll cnt[26]; CLR(cnt); FOR(i,0,len) cnt[A[i]-'a']++; ll ans = len * (len - 1) / 2; FOR(i,0,26) { if(cnt[i] >= 2) { ans -= cnt[i] * (cnt[i] - 1) / 2; } } cout << ans + 1 << endl; return 0; }