読者です 読者をやめる 読者になる 読者になる

ゆらのふなびと

競プロ, Python, C++

AOJ-ICPC 450 Encryption System

問題

Encryption System | Aizu Online Judge

解法

入力の文字列を s, 暗号化前の文字列をtとする

任意のiについて、t_i = s_i or s_i + 1 の2通りしかないので 220 の全探索が間に合う

左から見ていくと、t_i = s_i としてよいのは i の前に少なくとも1つ s_i と同じ文字があるとき

t_i = s_i + 1 としてよいのは i の前に1つも s_i + 1 と同じ文字がないとき

よって、(i, 構成中の文字列, 既に使われた文字)を引数とする再帰が書ける

やざてんさんのブログで見て気づいたけど、dfsの末尾で文字列をvectorに入れていくと勝手に辞書順になって最高

yazaten.hatenablog.com

gist.github.com