【よくわかる解説！】ABC345 C問題 〜上手く数える〜

解説動画はこちら！

コード

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (n); ++i)

// eC2の計算
ll cal(ll e) {
    return e * (e - 1) / 2;
}

int main() {
    string s;
    cin >> s;

    int n = s.size();
    vector alphabets(26);
    for (char c : s) alphabets[c - 'a']++;

    ll same = 0;
    for (ll e : alphabets) same += cal(e);

    ll ans = cal(n) - same;

    if (same) ans++;

    cout << ans << endl;
    return 0;
}

// 解説！
// abbccc

// 分かりやすく数字をつけて区別する
// a b1 b2 c1 c2 c3

// alphabets = [1, 2, 3, 0, ... , 0]

// 1. 全部のパターンを数え上げる
    // ダブりも込みで数える.
    // 例えば,「c1とc2」と「c1とc3」と「c2とc3」を選ぶをそれぞれ1通りとして数えている.
    // 6個の文字から2個選ぶ => 6C2 = 6 * (6 - 1) / 2 = 15

// 2. 同じ文字同士の入れ替えを数えてあげる. その後1.の結果から引く
    // ex)
        // b: 1通り (2個から2個選ぶ 2C2 = 1)
            // b1とb2
        // c: 3通り (3個から2個選ぶ 3C2 = 3)
            // c1とc2
            // c1とc3
            // c2とc3
// 3. 2.まで考慮すると,「元の文字列」になる1通りを数え漏れていることがあるので, それを加える.
    // 2.のパターンでの入れ替えでできる結果はどれもオリジナルの文字列 => abbccc

    // 他の例) abcdef <= どの2個を入れ替えても元の文字列と同じになることはない。