Kazun の競プロ記録

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

AtCoder Beginner Contest 226 B 問題 Counting Arrays

AtCoder ABC ABC226 B問題 200 pts

問題

提出解答

問題の概要

$N$ 個の数列 $A_1, \dots, A_N$ が与えられる. この中に登場する数列は何種類か?

制約

$1 \leq N \leq 2 \times 10^5$
各項は $1$ 以上, $10^9$ 以下
$N$ 個の数列の長さ (項の数) の総和は $2 \times 10^5$ 以下

解法

重複をまとめて1つにし, そうでない場合は別々のものを見るということは, 集合の味方に一致する. よって, 集合 $S:=\{A_1, \dots, A_N\}$ の濃度 $|S|, n(S)$ を求めることになる.