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

Share

AtCoder上にある問題のうち、AtCoder Problemsでdiff 800以上と判定されているものを順番に解いていく企画。
基本的な考え方は全てコード中のコメントに入れてあるので、参照のこと。

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

辞書順に何かを生成するときは、生成規則をきちんと作ってからやれば自然に辞書順になることが多い?

# パナソニックプログラミングコンテスト2020 D - String Equivalence
# https://atcoder.jp/contests/panasonic2020/tasks/panasonic2020_d
# tag: 文字列 辞書順 生成 考察

# ある任意の文字列を、標準形に変換することを考える。
# zyxzx の場合を仮に考える。

# 辞書順最少なので、一文字目は必ず a。また、全ての z に a を当てる。
# zyxzx
# a##a#

# 二文字目の y は初めて現れる文字なので、b を当てる
# ab#a#

# 三文字目の x は初めて現れる文字なので、c を当てる
# abcac

# つまり、異なる文字が現れる場合は、必ず a, b, c の順に
# 当てていく必要があるということ。

# さて、ある標準形 S に一文字付け加えることを考えると、
# S + (Sに含まれる一文字) もしくは
# S + (新しい文字、但し辞書順最少)
# ということになる。

# 以上を踏まえて、文字数をどんどん伸ばしていく方針で組んでみる。

def main():
    N = int(input())

    ab = 'abcdefghijklmnopqrstuvwxyz'

    # [現在の文字のリスト, 次の文字(数値)] を保存していく。
    standards = [[[], 0]]

    # 手持ちの標準形から、新たに一文字多い標準形を生成していく
    for i in range(N):
        nxt_std = []
        for c_list, nxt in standards:
            # すでに使用している文字を付け加えたもの
            for j in range(nxt):
                nxt_std.append([c_list + [ab[j]], nxt])

            # 初めての文字を付け加えたもの
            nxt_std.append([c_list + [ab[nxt]], nxt+1])

        # 持っている標準形を更新
        standards = nxt_std

    # 自動的に辞書順になっている
    for c_list, _ in standards:
        print(''.join(c_list))

main()

ついでに再帰DFSでも。やっていることはほぼ同じ。

# dfs を用いて再帰で順に生成することも出来る。
def main():
    N = int(input())
    ab = 'abcdefghijklmnopqrstuvwxyz'

    result = []

    def dfs(x):
        if x == 1:
            return [[0]]
        
        result = []

        for l in dfs(x-1):
            for i in range(max(l)+2):
                result.append(l + [i])

        return result
    
    for r in dfs(N):
        print(''.join(ab[i] for i in r))

main()
Share

コメントを残す

メールアドレスが公開されることはありません。