D - Unique Username

文字列の並べ替え方が $N!$ 通りです。

アンダーバーの入れ方ですが、まず、アンダーバーを入れる残り個数 $R$ は、文字数の合計を $sum$ とすると、 $R=16-(sum+N-1)$ です。

アンダーバーの入れ方は、区別のない $R$ 個のボールと区別のない $N-2$ 個の仕切りを並べる方法の総数に一致するので、 $_{R+N-2}C_{R}$ 通りです。

以上から、ありうるユーザー名の個数は、 $N!\times _{R+N-2}C_{R}$ 通りですが、いずれか一方が大きいともう一方は小さくなるので、少なそうだと予測できます。

厳密に全て確かめたい場合は、 $S_i$ の文字数が全て1の場合に最も個数が多くなるはずなので、 $N=1,...,8$ まで計算してみればよいかなと思います(コンテスト中はそこまでしませんでした)。

というわけで、全探索して問題なさそうです。(書いていて気づきましたが、個数が少ないとか関係なく、鳩の巣原理から $O(M)$ になりそうです。)

あとは、ユーザー名の生成方法です。
実装としては、順列全探索で文字列の並べ替え方を全部試し、その全てについてDFSでアンダーバーを付けていきました。詳細は実装を見てもらった方が早そうです。
Submission #34748520 - UNIQUE VISION Programming Contest 2022 Summer (AtCoder Beginner Contest 268)

geam1113’s diary