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; }