AtCoder Beginner Contest 345C問題

\(\def \set #1#2{\{ #1 \ \vert \ #2 \}}\)

ABC345C

解法

\(X := S\) から 1 swap で作れる string 全体の集合

とする．答えは \(|X|\).

• \(S \in X \iff\) for some \(i\) and \(j\) \(\in N\) such that \(i < j\) and \(S_{i} = S_{j}\)
• \begin{align} X - \{S\} &= \set{T}{for\,\,some\,\,i\,\,and\,\,j\,\,such\,\,that\,\,i\,\,<\,\,j\,\,and\,\,S_{i}\,\,\neq\,\,S_{j} and\,\,T\,\,is\,\,the\,\,string\,\,swap\,\,i\,\,and\,\,j\,\,on\,\,S}\,\,\\ &\cong \set{(i,j)\,\,\in\,\,N^{2}}{for\,\,some\,\,i\,\,and\,\,j\,\,such\,\,that\,\,i\,\,<\,\,j\,\,and\,\,S_{i}\,\,\neq\,\,S_{j}}\,\,\\ \end{align}

基本は \(X - \{S\} \) を数えればよく， \(S \in X\) のときだけ +1 すればよい．

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

int main() {

  string s; cin >> s;

  ll n = s.length();

  vll cnt(26);

  bool f = false;

  rep(i,n){

    cnt[s[i]-'a']++;

    if(cnt[s[i]-'a'] >= 2) f = true;

  }

  ll ans = f;

  ans += nC2(n);

  rep(i,26) ans -= nC2(cnt[i]);

  cout << ans << endl;

  return 0;

}