Kazun の競プロ記録

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

AtCoder Beginner Contest 247 B問題 Unique Nicknames

AtCoder ABC ABC247 B問題 200 pts

問題

提出解答

解法1

解法2

問題の概要

英小文字からなる $2N$ 個の文字列 $s_1, \dots, s_N, t_1, \dots, t_N$ がある. 次を満たすような $N$ 個の英小文字の組 $a_1, \dots, a_N$ は存在するか?

$i=1, \dots, N$ に対して, $a_i=s_i$ または $a_i=t_i$
$i=1, \dots, N$ に対して, 以下が成立: $1 \leq j \leq N$ かつ $i \neq j$ を満たす全ての整数に対して, $a_i \neq s_j, a_i \neq t_j$

制約

$2 \leq N \leq 100$
$s_i, t_i$ は長さ $1$ 以上 $10$ 以下の英小文字からなる文字列.

解法1 (愚直)

条件の通りに $i=1,2, \dots, N$ の順に $a_i=s_i$ としても問題ないか, $a_i=t_i$ としても問題ないかをそのまま調べ, どちらか一方でも満たせば $i$ のときは条件を満たす. これが全ての $i$ について成立すれば肯定的解決であり, 1つでも満たさなければ否定的解決である. 時間計算量は $O(N^2)$ である.

解法2 (個数計上)

英小文字列 $u$ に対して, $\chi(u)$ で以下を満たす $i$ の個数とする.

$s_i=u$ または $t_i=u$

このとき, $i$ において条件を満たすための必要十分条件は $\chi(s_i)=1$ または $\chi(t_i)=1$ である.

時間計算量は $O(N)$ である.