AOJ 1195 - 暗号化システム
解法
最悪ケースを考えると、サンプルにあるような17711通りのパターンになります。
ということで、全部列挙してから文字列をソートし、10個出力するのが十分間に合います。
あとは、全部列挙する方法を考えていけばよいです。
操作終了後の文字列が与えられているので、後ろから復元していくことを考えます。
yをxに操作した直後の文字列について考えます。
ということで、現在の文字列にxが存在していれば、そのxのうちどれか1つをyに直していけばよく、存在していなければ、何も操作は起こらないです。
が、現在の文字列にyが存在している場合、それより後ろ側のxをyに戻しても、実際に行われる操作と、今想定している操作の対象の文字が矛盾してしまいます(すでに存在しているyに対して操作が行われてしまい、xを戻して作成したyに対して操作は行われません)。
ので、現在の文字列にすでにyが存在していた場合は、それ以前のxに対して必ず操作を行う必要があります。
この部分にのみ注意をして、文字列を全て復元すればよいです。
感想
xをyに戻してあげるときに、すでにyが存在していたパターンの処理に迷ってしまいました。丁寧に実験してあげることが重要そうです。
