Kazun の競プロ記録

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

AtCoder Beginner Contest 268 D問題 Unique Username

AtCoder ABC268 ABC D問題 400 pts

問題

提出解答

問題の概要

次を満たす文字列 $X$ が存在するならば一例を挙げ, 存在しなければその一例を挙げよ.

は次のようにして構成されている.
1. $S_1, \dots, S_N$ の並び替え1つ取ってきて, それを $S'_1, \dots, S'_N$ とする.
2. $X=S'_1 \oplus$ ( $1$ 個以上の ${\tt \_}$ ) $\oplus \cdots \oplus$ ( $1$ 個以上の ${\tt \_}$ ) $\oplus S'_N$
$3 \leq |X| \leq 16$
$X$ は $T_1, \dots, T_M$ のどれとも一致しない.

制約

$1 \leq N \leq 8$
$0 \leq M \leq 10^5$
$1 \leq |S_i| \leq 16$
$(N-1)+|S_1|+\dots+|S_N| \leq 16$
$i \neq j \Rightarrow S_i \neq S_j$
$S_i$ は英小文字からなる文字列
$3 \leq T_i \leq 16$
$i \neq j \Rightarrow T_i \neq T_j$
$T_i$ は英小文字と ${\tt \_}$ からなる文字列

解法

乱択解法について説明する.

$K:=|S_1|+\dots+|S_N|$ とする. このとき, 最初の条件を満たすような文字列の個数はアンダーバーの挿入する場合が $H(16-K-(N-1), N-1)=\dbinom{16-K}{N-1}$ なので, $A:=N! \times \dbinom{16-K}{N-1}$ 通りである.

このとき, $A$ が $M$ 以下だったり, $M$ より大きくても十分近かった場合は $M \leq 10^5$ より, 一番上の条件を満たすような文字列を何回かランダムに生成すればいずれかヒットするし, $A$ が $M$ より十分大きい場合はある程度の回数ランダムに生成すればヒットする.

よって, 一番上の条件を満たす文字列をランダムに生成し, 許容できればその文字列を返し, 許容できなければやり直しとし, 制限時間が来たら "存在しない" とすると高い確率 (?) で正解できる.

なお, $N=1$ のときの場合に注意せよ.