【AtCoder】ABC 429 C - Odd One Subsequence

2025-10-30

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 201 / NoviSteps: 3Q / 配点: 300 点

問題概要

長さ $N$ の整数列 $A$ が与えられる。 $1\leq i < j < k \leq N$ を満たす整数の組 $(i,j,k)$ であって、次の条件を満たすものの個数を求めよ。

$A_i,A_j,A_k$ の中にちょうど $2$ 種類の値が含まれる。

制約

$3 \leq N \leq 2\times 10^5$
$1 \leq A_i \leq N$
入力はすべて整数

考察

$A$ の中に 2 回出現する値 $v$ を固定して考える。

事前に $A$ に出現する要素の個数を連想配列などで数えておき、値 $v$ の出現回数を $c_v$ とする。

ある値 $v$ に注目したとき、

$A$ から $v$ を 2 個選ぶ選び方は $\binom{c_v}{2}$ 通り
$A$ の中で $v$ 以外の要素を選ぶ選び方は $N - c_v$ 通り

であるから、この $v$ によって得られる条件を満たす整数組 $(i,j,k)$ の個数は

\binom{c_v}{2} \times (N - c_v)

となる。ただし、 $c_v < 2$ の場合は $v$ を 2 個選ぶことができないので $0$ とする。

これを $A$ に出現する全ての値 $v$ について求めて総和を取ればよいので、求める答えは

\sum_{v=1}^N \binom{c_v}{2} \times (N - c_v)

となる。

実装例

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
5.#define repe(i, start, end) for (auto i = (start); (i) <= (end); (i)++)
6. 
7.using ll = long long;
8. 
9.// ======================================== //
10. 
11.int main()
12.{
13.    int N;
14.    cin >> N;
15.    map<ll, ll> mp;
16.    rep(i, 0, N)
17.    {
18.        ll A;
19.        cin >> A;
20.        mp[A]++;
21.    }
22. 
23.    ll ans = 0;
24.    repe(v, 1, N)
25.    {
26.        if (mp[v] < 2)
27.            continue;
28. 
29.        ll pair = mp[v] * (mp[v] - 1) / 2;
30.        ll other = N - mp[v];
31.        ans += pair * other;
32.    }
33. 
34.    cout << ans << endl;
35. 
36.    return 0;
37.}