アナグラム [第四回 アルゴリズム実技検定 E]

https://atcoder.jp/contests/past202010-open/tasks/past202010_e

解説

https://atcoder.jp/contests/past202010-open/submissions/21471881

この問題で一際目立つ特徴といえばNの最大値が5である。
極端に制約が小さいので全探索をまずは疑おう。

何を全探索する？間に合うのか？

今回の答えTはSの文字を並び替えて作ることができるため、Sの文字を並び替えてできるすべての文字列が
答えの候補となる。
これを全探索しよう。
Sの文字を並び替えて作ることができる組みあわせは最大5文字であれば、5!通りである。
120通りで余裕。

どうやって全探索するか

この問題で最も難しいのは「Sの文字を並び替えて作ることができる文字列の列挙」である。
この操作が最も難しい…

C++であれば、next_permutationを使えばとても簡単に全列挙ができる。
自分はこれでサクッとやってしまっている。

他の言語でも同様のものがあるかもしれない。調べていないが。

自分でこのあたりを実装するとしたらdfsを使った全列挙をすることになるのではないかなと思う。
「順列列挙」くらいで調べると色々出てくる。

int N; string S, T;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> S;
    T = S;
    sort(all(T));

    do {
        string TT = T;
        reverse(all(TT));

        if (S != T && S != TT) {
            cout << T << endl;
            return;
        }
    } while (next_permutation(all(T)));

    cout << "None" << endl;
}