パナソニックプログラミングコンテスト 2020 D – String Equivalence

この問題では、英小文字からなる文字列のみを考えます。

文字列 $s,t$ は以下の条件を満たすとき 同型 であるといいます。

・ $|s|=|t|$ である。
・任意の $i, j$ に対し次のいずれかが成立する。
　・ $s_i=s_j$ かつ $t_i=t_j$
　・ $s_i \neq s_j$ かつ $t_i \neq t_j$

たとえば、abcac と zyxzx は同型ですが、abcac と ppppp は同型ではありません。

文字列 $s$ は以下の条件を満たすとき 標準形 であるといいます。

・任意の $s$ と同型な文字列 $t$ に対し、$s \leq t$ が成立する。ただしここで $\leq$ は辞書順での比較を表す。

たとえば、abcac は標準形ですが、zyxzx はそれより辞書順で小さい　abcac と同型のため標準形ではありません。

整数 $N$ が与えられます。 長さ $N$ の標準形の文字列を全て、辞書順で昇順で出力してください。

https://atcoder.jp/contests/panasonic2020/tasks/panasonic2020_d

解いていて、大学の授業でやった生成文法とかそのへんの話を思い出しました。

試しに $N = 1$ あたりから実験をしてみたいと思います。すると

# N = 1
a

# N = 2
aa
ab

# N = 3
aaa
aab
aba
abb
abc

# N = 4
aaaa
aaab
aaba
aabb
aabc
abaa
abab
abac
abba
abbb
abbc
abca
abcb
abcc
abcd

実際に手を動かしてみるとよく分かるのですが、どうやら $N = k+1$ の答えは $N=k$ の答えの後ろに 1 文字を足してやることで得られそうな気がします。

これを細かく言語化してみます。以下具体例は $N=2 \to 3$ で考えてみます。

まず、"aa" から "aaa", "aab" が、 "ab" から "aba", "abb", "abc" がそれぞれ生成されると考えることができます。

文字列 "aa" で例を挙げながら考えると、これらは各文字列 "aa" のうしろに、アルファベットで "aa" に使われているもの + 1 つの種類の文字をつけてあげることで生成されそうです。

こんな感じでコードに起こせそうです。

["生成元の文字列" + x for x in alphabet[:len(set("生成元の文字列")) + 1]]

この処理を、生成元の各文字列に対して行えばよいことがわかります。

同様のルールで、 $N=1$ の答え "a" から繰り返し生成の処理を適用させることでイケそう。結局こんな感じで実装すれば OK です。

N = int(input())
ans_list = ["a"]  # 生成元の初期状態 (N = 1 の答え)
alphabet = [chr(ord("a") + i) for i in range(N)]  # 使用するアルファベット

for i in range(N - 1):
    ans_list = [ans + x for ans in ans_list for x in alphabet[:len(set(ans)) + 1]]

for ans in ans_list:
    print(ans)

サトゥー

「生成のイメージ」の画像を繰り返し適用して伸ばしていくと木構造が得られるので、それを探索するイメージで DFS でもイケそうですね。