mini notes

競技プログラミングの解法メモを残していきます。

DigitalArts プログラミングコンテスト2012 B - Password

問題:B - Password

解答:Submission #11252972 - DigitalArts プログラミングコンテスト2012

解法:aもしくはz*20の場合は同じハッシュ値を持つパスワードがないのでNO。それ以外は次のように生成する。

①1文字でa以外:1文字をXとすると(X -1)aの2文字とする(例:d → ca)

②2文字から19文字で全部a:'a' + aの個数 - 1の文字(例:aaa → c)

③2文字から19文字でa以外がある:最小に現れるa以外の文字をXとするとその部分を(X-1)aにする。(例:abc → aaac)

④20文字で全部a:②と同じ

⑤20文字で④でない、かつ全部zでない:aでない文字Xを(X-1)にし、zでない文字Yを(Y+1)にする

⑤はコーディングによってはバグを埋め込むので注意。(最大の文字をX-1、最小の文字をY+1とした方がよかった)