Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 295 C問題 Socks

AtCoder ABC ABC295 300 pts C問題

問題
提出解答
問題の概要
- 制約
解法

問題

提出解答

問題の概要

$N$ 枚の靴下がある. $i$ 番目の靴下の色は $A_i$ である.

同じ色の靴下 $2$ 枚のペアは最大でいくつできるか?

制約

$1 \leq N \leq 5 \times 10^5$
$1 \leq A_i \leq 10^9$

解法

整数 $a$ に対して, $A_1, \dots, A_N$ にある $a$ の数を $\chi(a)$ と書くことにする. このとき, 正解は

$\displaystyle \sum_a \left \lfloor \dfrac{\chi(a)}{2} \right \rfloor$

である.

このとき, $a=A_1, \dots, A_N$ に対する $\chi(a)$ は連想配列を利用することによって, $O(N)$ 時間で求めることができる.