AOJ 暗号化システム - やむなく日記

これめっちゃ難しく考えてしまった…

各文字は1回しか変わらないから異なる文字列は高々2^20個しか登場しない

与えられた文字列から逆の操作をして、もとの文字列へ復元したい

逆の操作で作れる文字列を全列挙していけばいいとなって泥沼にはまった…

[いらなかった考察]

与えられた文字列をtとして、もとの文字列をsとする

i番目の文字s[i]をt[i]からt[i]-1に変更できる条件は、s[j]==t[i]であるすべての j (i<j)についてs[j]は変更済み(すなわちt[j]==t[i]+1)であること

s[i]をt[i]のままにできる条件は、s[j]がt[i]-1である j (j<i)が存在して、s[j]は変更済み(すなわちt[j]==t[i])であること

逆の操作で作れた文字列とその各文字を変更したかどうかのフラグをペアにして、setとかに入れて管理すればなんとかできる

[考察ここまで]

この考察は記事にするときに一度整理されたもので、解いている間は1番から逆の操作をやってみたり、各位置の文字がそれぞれ1度しか変更されないことを意識できに復元中の文字列sの文字種だけに注目していたりと破滅していた

ググったら何も考えなくても解ける賢い方法が出てきて、2^20通りの文字列すべてを暗号化して、与えられたものと一致するか見ていけばいいらしい

やられた