Codeforces Beta Round #95 (Div. 2) B :Opposites Attract

問題概要

配列X(|X|=:N<10^5, |X[i]| <= 10)が与えられる。i!=jについて、X[i] == -X[j]ならペアを為す。ペアがいくつあるか求める問題。

解法

X[i]の値の分布を調べておくだけ。0は例外処理する。

本番で通ったコード

計算量O(N+MAX_X)。

#include <cstdio>
#include <iostream>
using namespace std;

typedef long long int64;

const int MAX_N = 100000;
const int MAX_T = 10;

int N;
int ins[2*MAX_T + 1], *ts;

int64 solve(){
	int64 ans = 0;

	for(int i=1; i<=10; i++){
		ans += (int64)ts[i] * ts[-i];
	}

	if(ts[0] > 1){
		ans += (int64)ts[0] * (ts[0] - 1) / 2;
	}

	return ans;
}

int main(){
	ts = ins + 10;

	scanf("%d", &N);
	for(int i=0; i<N; i++){
		int x;
		scanf("%d", &x);
		ts[x]++;
	}
	cout << solve() << endl;
	return 0;
}