2つの数の和 [yukicoder No.723]

https://yukicoder.me/problems/no/723

解法

https://yukicoder.me/submissions/276742

こういう数え上げ問題のよくある手法を使う。
ある条件を満たす項目数を前計算しておくというテク。
今回はcnt[a] := A[i]=aを満たす項目数を前計算しておく。
条件を満たす組(i,j)を考えるが、iを固定すると、jの方で満たすべき条件はA[j] = X - A[i]である。
よって、iを固定したときのjの組み合わせ数はcnt[X-A[i]]となる。
X-A[i]が0以上10^5以下であることを確認しないと、配列外参照となるので実装に注意しよう。

int N, X, A[101010];
int cnt[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> X;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) cnt[A[i]]++;

    ll ans = 0;
    rep(i, 0, N) {
        int d = X - A[i];
        if (0 <= d and d <= 100000) ans += cnt[d];
    }
    cout << ans << endl;
}