Reverse and Compare [AtCoder Grand Contest 019 B]

http://agc019.contest.atcoder.jp/tasks/agc019_b

解法

http://agc019.contest.atcoder.jp/submissions/1547643

エスパーして解く。
本番では回分数を数えて、全体から引くのだと思っていたが、これだとあまりに500点には難しい。
順位表を眺めて見ても法外に早い時間で解いている人がいたり、青コーダーの方も通しているので、発想問題であると想像できる。
簡単に計算ができそうなものを考えてみると、「A[i] != A[j]である(i,j)の組み合わせ+1」が答えっぽい。
これでサンプルが全て合うので、出してみると通る。
　
A[i] != A[j]である(i,j)の組み合わせ
これは後ろから、cnt[i] = アルファベットi番目(0番目はa,1番目はb,...)を更新しながら数えていく。
後ろからやることでcnt配列には、その文字よりも後ろのアルファベットの出現個数が入っていることになる。
あとは、A[i]以外のアルファベットの個数を毎回答えに足し合わせていけば良い。

typedef long long ll;
string A;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> A;
    int N = A.length();
 
    vector<int> cnt(26);
    ll ans = 1;
    rrep(i, N - 1, 0) {
        rep(j, 0, 26) if (j != (A[i] - 'a')) ans += cnt[j];
        cnt[A[i] - 'a']++;
    }
    cout << ans << endl;
}