Kazun の競プロ記録

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

AtCoder Beginner Contest 302 C問題 Almost Equal

AtCoder ABC ABC302 C問題 250 pts

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

問題

提出解答

問題の概要

$N$ 個の長さ $M$ の英小文字列 $S_1, \dots, S_N$ がある.

この $N$ 個の文字列の並び替え $T_1, \dots, T_N$ のうち, 以下を満たす並び替えは存在するか?

全ての $i=1,2, \dots, N-1$ に対して, $T_i$ を $1$ 文字だけ別の英小文字列にすることで, $T_{i+1}$ にすることができる.

制約

$2 \leq N \leq 8$
$1 \leq M \leq 5$
$S_1, \dots, S_N$ は長さ $M$ の英小文字列

解法

まず, $X$ を $1$ 文字だけ別の英小文字列にすることで, $Y$ にすることができるための必要十分条件は, $X,Y$ において, 異なる場所がただ $1$ だけであることである.

また, $S_1, \dots, S_N$ の並び替え $T_1, \dots, T_N$ の数は $N!$ 通りである.

$N \leq 8$ であるから, 各並び替えに対して, 条件を満たすかどうかを愚直に判定することによって, 全体で $O(NM \times N!)$ 時間で求めることができる.