Squared Error [AtCoder Beginner Contest 194 C]

https://atcoder.jp/contests/abc194/tasks/abc194_c

前提知識

• 主客転倒テク

解説

https://atcoder.jp/contests/abc194/submissions/20735087

言ってるの自分と物理好きさんだけかもしれないんだけれど、主客転倒テクを使う。
今回の問題はAの全組合せに対して差分の二乗を取った総和をとる問題である。
このままだと、Aの全組合せは10¹⁰通りくらいあって間に合わないので何とかする必要がある。
ここでよく取られるテクが主客転倒テク。

主客転倒

Aの全組合せを考えるのは難しいのだけれど、総和を取られる差分の二乗は実はそんなに組合せが無い。
具体的にはAの値が-200≦A≦200なので、400通りくらいしかないので、差を取る組合せが160000で10⁵通りくらいとなり、
こちらは全く問題がない。
よって、問題を以下のように変更して考えよう。

Aの全組合せに対して「差分の二乗」を取った総和
↓
「差分の二乗」×「その差分となるAの組合せ数」の総和

このように足される側を全探索するように視点を変えるようなテクを主客転倒と言う。

より実装寄りの話をする。
cnt[x] := A[i]=xとなるiの個数
という風に種類ごとに集計しておくと、
差分の二乗は(x-y)²となり、
その差分となるAの組み合わせ数はcnt[x]*cnt[y]となる。
これで、あとは使われたAの種類を全探索して、すべての組について考えていけばいい。

注意

問題文を見ると、A[i]-A[j]かつi>jのように順番が違うだけのものは除外して考えているので、
それは除外すること。
自分の実装では問題文と全く同じ除外方法にはなっていないのだが、差分の二乗を利用しているので実質同じである。
自分のようにループ内で除外するのではなく、全通り計算してしまって答えを半分にしても問題ない。

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

    map<int, int> cnt;
    rep(i, 0, N) cnt[A[i]]++;

    ll ans = 0;
    fore(p1, cnt) fore(p2, cnt) {
        if (p1.first > p2.first) continue;
        if (p1.first == p2.first) continue; // due to dans = 0
        // p1.first < p2.first

        ans += 1LL * (p2.first - p1.first) * (p2.first - p1.first) * p1.second * p2.second;
    }
    cout << ans << endl;
}