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

問題

長さNの、英小文字からなる文字列を考える。
ある文字列sとtは、以下の条件の時「同型」という。

• |s| = |t|
• 任意のi,jに対して以下のいずれかが成り立つ
  • s[i]==s[j] かつ t[i]==t[j]
  • s[i]!=s[j] かつ t[i]!=t[j]

また、文字列の標準形とは、

• 任意のsと同型な文字列tに対し、s<=t(辞書順)が成り立つ

このとき、長さNの標準形をすべて辞書順かつ昇順で出力せよ。

制約

• 1 <= N <= 10

解法

N=1と2はサンプルにあるので、N=3のときの標準形を考えてみる。

1種類～3種類までの文字を考えると、

1種類
aaa
(bbbはaaaがあるので標準形ではない)
2種類
abb
aab
aba
(baa, bab,bbaは標準形ではない)
3種類
abc
(bac,bca,cab,cbaは標準形ではない)

したがって、

aaa
aab
aba
abb
abc

の5パターンが考えられる。

next_permutationなど、単純に生成しようとしてしまうと、無駄な重なりを含めて生成してしまうため、時間がかかってしまう。

ここで、生成された文字列から法則を考えてみると、

最初の文字は'a'でなければならない。('b'以降の文字が来る場合はそれを'a'にすることができてしまうため)
次の文字は、'a'か、または、'b'でなければならない。('c'以降の文字が来る場合はそれを'b'にすることができてしまうため)
同様に、その次の文字は、'a'か'b'か'c'でなければならない。
が、それまでに使った文字が'a'のみの場合は、'a'か'b'でなければならない。
・・・

のような規則があることがわかる。
したがって、それまでに使った文字で最大の文字+1の文字が次に使えることがわかる。