D. String Equivalence 緑コーダーですが何か？その５

緑のしいだよ。今年のトレンドは明るめのグリーンだから流行の最先端だよ。 緑コーダーですが何か？第5回目！

深夜で眠いけど一問はとくよ 今宵の一問はこれ D. String Equivalence

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

問題文の意味が難しくてずっと先延ばしてた問題なんだけど、頑張って理解していきましょう。

解法

---

パッとみたところ制約のNが最大でも10なのでやりたいことし放題だね。 DFSをつかって文字列を生成していったらできそうだね。

ところで、今回大事なのが任意の同じ形に対して最小のものを集めた辞書を作るということ。 つまり

‘ab’ ‘ac’

は同じものだから’ac’の方を出力したらまちがいになる。

ということで

    a = int(input())
    S = 'abcdefghij'
    def dfs(s,c):
        if c == a:
            ans.append(s)
            return 
        for i in S[:c+1]:dfs(s+i,c+1)

こういうループは書いてはいけないのだ。

注意すべきなのは追加する文字が元の文字列に入っているものなのかどうかを判断して追加してあげないといけないね。

以下がACコード

実装

---

    a = int(input())
    S = 'abcdefghij'
    def dfs(s,c):
        if c == a:
            ans.append(s)
            return 
        for i in S[:c+1]:
            if i in s:dfs(s+i,c+1)
            else:
                dfs(s+i,c+1)
                return 
    ans = []
    dfs("",0)
    for i in ans:
        print(i)

あとがき

---

結構スッキリ実装できて満足 DFSを使うのも慣れてきてうれしい😆