atcoder abc194 C - Squared Error

問題

C - Squared Error

解法

Nの制約が $ 2 ≤ N ≤ 3 × 10 ^ 5 $ のため $ i,j $ の組み合わせを全探索すると $ O ( N ^ 2 ) $ で間に合わない。

そこで制約の $ |A_i| ≤ 200 $ に注目する。$ |A_i| $ の取る値は -200〜200 の範囲となっていて小さいことがわかる。 これを利用して-200〜200の範囲で取りうる値をすべて試せば良い。

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

int main() {
  int n; cin >> n;
  map<int,int> m;
  REP(i,n) {
    int a; cin >> a;
    m[a]++;
  }

  ll ans = 0;
  for(int i = -200; i <= 200; i++) {
    for(int j = i+1; j <= 200; j++) {
      ans += pow(i-j,2)*m[i]*m[j];
    }
  }

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

雑感

• 制約条件が小さいときはそれを利用できないか考えてみる