ABC 401-500/ABC416C - Concat (X-th) - 競技プログラミング用 知識集積所【7/27更新】

---

問題

ABC416C
入力例が不親切なので注意

追加入力例

入力例3

2 3 1
x xo

出力例3

xoxox

辞書順に並べると "xoxox", xoxoxo", "xoxx", "xoxxo", "xxox", "xxoxo", "xxx", "xxxo" です。

必要知識

B以下レベルの内容は省略

• bit全探索（未作成）の一般化
• 基数変換（未作成）

考え方

文字列のパターンの最大数が、全部で10万通り。
文字数の最大値が50。

ということは、可能な文字列を全部作ってソートするとして、必要な計算回数は

• 全部作るのに500万回
• ソートに10^5*log(10^5)*1回の比較で最悪50文字分=8300万回

なので、1秒くらいで間に合う。

※
1秒くらいかかる……はずなのだが、実際に実行すると最悪の入力でも20msくらい。
vector<string> のソートが何か特殊な方法で実装されているのかもしれない。

問題は、可能な文字列を全部作ってソートする方法。
愚直なforループは、kの値によって何重ループにするかが不定なので厳しい。
（kの値によってif分岐で5つにわける力業ができなくもない）

そこで、nの値に注目して考えてみる。
もしnが2であれば、これはbit全探索（未作成）でいける。
つまり、2択k回を、まとめて2^k以下の整数で表して探索ができる。

となれば、n択k回は、まとめてn^k以下の整数で表せば探索ができると考えられる。
bit全探索（未作成）のようにbit演算（未作成）で処理することはできないが、原理がしっかりわかっているなら基数変換（未作成）で代用してやればよいだけである。

解答例

解答例

注意点

n=1の場合に注意

1進数というものは存在しない。
基数変換のところで変な挙動にならないか、自前で用意してテストすること。

別解

深さ優先探索（未作成）を使う

全文字列を作成するのに、深さ優先探索（未作成）を使うこともできる。
解答例