Kazun の競プロ記録

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

AtCoder Beginner Contest 272 B問題 Everyone is Friends

AtCoder ABC272 ABC B問題 200 pts

B# 問題 atcoder.jp

提出解答

問題の概要

人 $1, \dots,$ 人 $N$ の $N$ 人がいる.

この $N$ 人はそれぞれ $M$ 回開かれた舞踏会に $0$ 回以上参加した.

$j$ 回目の舞踏会では人 $x_{j,1}, \dots, x_{j, k_j}$ が参加した.

次が成り立つか?

どの2人も少なくとも1回同じ舞踏会に参加した.

制約

$2 \leq N \leq 100$
$1 \leq M \leq 100$
$2 \leq k_j \leq N$
$1 \leq x_{j,1} \lt \dots \lt x_{j,k_j} \leq N$

解法

集合 $S_1, \dots, S_N$ を次のように定める.

人 $j$ が参加した舞踏会 (の番号) 全体の集合を $S_j$ とする.

ここで, 人 $i$ と人 $j$ が共に参加した舞踏会が存在することの必要十分条件は共通部分 $S_i \cap S_j$ が空集合にならないことである.

よって, この条件を $1 \leq i \lt j \leq N$ となる全ての整数の組 $(i,j)$ について確かめてあげれば良い.

$S_1, \dots, S_N$ の管理については長さ $N$ のリストか集合などのデータ構造を利用することで実装できる.