Swappable [AtCoder Beginner Contest 206（Sponsored by Panasonic） C]

https://atcoder.jp/contests/abc206/tasks/abc206_c

解説

https://atcoder.jp/contests/abc206/submissions/23625007

まず、i,jの組を全探索する方針があるが、これは9*10¹⁰通りとなるので間に合わない。
全探索系は10⁷くらいが上限。
だが、片方だけ全探索するのは間に合う。
片方を全探索して、もう片方は効率よく求める方針で解いていこう。

jを全探索する

iでもいいのだが、i＜jの場合はjを全探索する方針で自分は良く解いている。
逆を全探索しても本質は特に変わらない。

jを固定化したときに条件を満たすiの個数を高速に求めることができれば、その総和を取れば答えになる。
条件はA[i] != A[j]であるが、今回は余事象を使うことにしよう。
つまりA[i] == A[j]を使うということだが、以下のように考える。

(条件を満たすiの個数)
= (全体) - (条件を満たさないiの個数)
= j - (A[i] == A[j]となるiの個数)

i,jを0-indexedで考えているので、全体はjとなっている。
上記の式までをまずは理解しよう。

とある値となるiの個数

これを高速に求めるためにC++ではmapを使おう。
mapを使って以下の配列を用意しておく。

cnt[x] := A[i]=xとなるiの個数

これをjを0から探索していくときに同時に更新していくことで、
とあるjを計算するときには「0～j-1のA[j]について、cnt配列が構築されている」状態を維持することができる。
なので、jを評価する時点でのcntはj未満の結果、つまり、i＜jの条件を満たした状態の結果が入っていることになる。
よって、cnt[A[j]]がA[i] == A[j]となるiの個数として使えることになる。

後は、実装を頑張る。
mapが使えない場合は座標圧縮というテクを使って普通の配列に乗る様に頑張る必要があるが、座標圧縮を知らない場合はmapを勉強する方がたぶん早い。
あと、C++になじみがない人向けに書くと、mapは辞書配列のことである。

int N, A[301010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];

    map<int, int> cnt;
    ll ans = 0;
    rep(j, 0, N) {
        ans += j - cnt[A[j]];
        cnt[A[j]]++;
    }
    cout << ans << endl;
}