Kazun の競プロ記録

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

AtCoder Beginner Contest 282 B問題 Let's Get a Perfect Score

AtCoder ABC282 ABC B問題 200 pts

問題

提出解答

問題の概要

$N$ 人の参加者が $M$ 問の問題に挑戦する.

$S_i[j]={\tt o}$ のとき, 参加者 $i$ は問題 $j$ を解くことができる. $S_i[j]={\tt x}$ のとき, 参加者 $i$ は問 $j$ を解くことができない.

次を満たす $1 \leq x \lt y \leq N$ である整数の組 $(x,y)$ の数を求めよ.

$1$ 以上 $M$ 以下の任意の整数 $j$ について, 参加者 $x$ または参加者 $y$ は問題 $j$ を解くことができる.

制約

$2 \leq N \leq 30$
$1 \leq M \leq 30$
$S_i$ は ${\tt o}, {\tt x}$ からなる長さ $M$ の文字列.

解法

集合 $U$ を $U:=\{1,2, \dots, M\}$ とし, 集合 $E_1, \dots, E_N$ を次のようにして定める.

$E_i:=\{j \in U \mid S_i[j]={\tt o} \}$

このとき, $(x,y)$ が条件を満たすことと, $E_x \cup E_y=U$ であることが同値になる.

よって, $E_1, \dots, E_N$ を集合というデータ構造で記録し, 和集合を取って実際に確認することによって, 求めるべき組の数を $O(N^2 M)$ 時間で求めることができる.