[BOJ]1759-パスワードの作成


展開

に近づく


条件を満たすパスワードを予め順番に出力します.
質問を見た瞬間、NとM(2)に似た質問だったと思います.そこで、上記の問題の解決方法を参考に、復帰によって解くことにしました.
NとM(2)の問題とは異なり,出力文字列には条件(文字/アクセント数の制限)が付加されている.
これらの条件をどうするかを考慮して、候補者を選択する前に条件を満たすかどうかを確定してからコードを書くことにします.

コード#コード#

from sys import stdin

def make_str(next_idx, jaum, moum):
    global L, C, alphabets, answer, passwd

    if len(passwd) == L and jaum <= 0 and moum <= 0:
        answer.append(passwd)
        return

    if next_idx == C:
        return

    for i in range(next_idx, C):
        is_moum = alphabets[i] in ('a', 'e', 'i', 'o', 'u')
        passwd += alphabets[i]
        make_str(i + 1, jaum-1 if not is_moum else jaum, moum-1 if is_moum else moum)
        passwd = passwd[:-1]


L, C = map(int, stdin.readline().split())
alphabets = stdin.readline().strip().split()
alphabets.sort()

passwd = ""
answer=[]
make_str(0, 2, 1)

for i in answer:
    print(i)
jaummoumその意味は正しいと思う(…).基本フレームワークはNとM(2)と同じですが、ソートされていないと入力しますので、先にソートします(この方法で事前ソートするには、元のデータをソートする必要があります).また、候補文字列作成時に子音・母音条件を監視しながら、完了時に(len(passwd) == L)条件が満たされているかを確認する.

ヒント


かなり難易度の高い問題かと思いきや、以前の問題で使われていた策略を実際に応用して、すぐに解決してしまい、少し慌てていました.自分で問題を解くフィードバックが勉強に役立つことを証明した.軍旅生活の劣悪な条件の下で、少しでも発展しているのは感謝に値する.