パナソニックコン2020 D - String Equivalence

問題原文

atcoder.jp

問題要旨

英子文字からなる文字列 を考える。
文字列 , を以下の条件を満たす時に、『同型』と呼ぶことにする。

• 長さが同じ
• のある場所の２文字が同じなら、 の同じ場所のペアも同じ文字。
• のある場所の２文字が異なるなら、 の同じ場所のペアも異なる文字。
• 例えば、 abcac と zyxzx は同型。

また、ある文字列 について、 全ての同型な文字列よりも辞書順で小さいものを『標準形』と呼ぶことにする。
長さ の文字列の標準形を辞書順で全て求めよ。

• 

解法

すごい面倒そうな全探索が必要な雰囲気。
[tex: 10²⁶] 通りの全列挙はできないので、何か考える必要がある。

まず、アルファベットの11番目以降の文字は標準形に組み込まれないことがわかる。
それをさらに詰めると、標準形になりうる文字は abcdefghij のみであって、各文字の最初の出現位置は必ずこの順番になることがわかる。
（例えば、 abcdiii なんてのは、 abcdeee でよいので）

次に、いろいろ実験をすると、
「標準形の文字列に、その標準形の文字列中に出現する文字、あるいは辞書順で最も大きいものの次の文字を加えたものも標準形」ということに気付ける。
例えば、 ab に a を加えた aba は標準形で、 bを加えたabb も標準系である。さらに、 ab の maxであるb の次の文字である c を加えた abc も標準形であることがわかる。

よって、 文字の標準形を得るには、 文字の標準形があれば十分なことがわかる。

実装

N = int(input())
X = [chr(ord('a') + i) for i in range(N)]
first_presence = {x: i for x, i in zip(X, list(range(N)))}
 
R = ['a']
for i in range(1, N):
    next_r = []
    for r in R:
        max_s = max(r)
        for x in X[:first_presence[max_s] + 2]:
            next_r.append(r + x)
    R = next_r
 
ans = R
ans.sort()
print(*ans, sep="\n")

感想

問題自体は決して難しく無いけど、きちんと詰めないと簡単にWAを吐く。 200, 300で散々やられて（あるいはパスをして）ここでペナを吐くと本当に気が気でなくなる。
本番よく通したな。。。