Kazun の競プロ記録

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

AtCoder Beginner Contest 279 C問題 Random

AtCoder ABC279 ABC C問題 300 pts

問題

提出解答

問題の概要

長さ $W$ の $2H$ 個の ${\tt \#}, {\tt .}$ からなる文字列 $S_1, \dots, S_H, T_1, \dots, T_H$ が与えられる. 次を満たすような $(1,2, \dots, W)$ の順列 $P=(P_1, \dots, P_W)$ は存在するか?

$1 \leq i \leq H, 1 \leq j \leq W$ に対して, $S_{i,P_j}=T_{i,j}$

制約

$S_i, T_i$ は ${\tt \#}, {\tt .}$ からなる長さ $W$ の文字列.

解法

$2W$ 個の長さ $H$ の文字列 $A_1, \dots, A_H, B_1, \dots, B_H$ を次のように定める.

$A_j:=S_{1,j} S_{2,j} \dots S_{H,j}$
$B_j:=T_{1,j} T_{2,j} \dots T_{H,j}$

すると, 問題は $(A_1, \dots, A_W)$ を並び替えて $B:=(B_1, \dots, B_W)$ にできるか? という問題に帰着できる.

この問題を解く方法として, $(A_1, \dots, A_W)$ を辞書式の観点でソートした列を $A':=(A'_1, \dots, A'_W)$ とする. このとき, 可能であることの必要十分条件は $A'=B$ である.

ソートの部分がボトルネックになり, $W$ 個の長さ $H$ の文字列をソートするので, $O(HW \log W)$ 時間になる.