String Equivalence [パナソニックプログラミングコンテスト2020 D]

https://atcoder.jp/contests/panasonic2020/tasks/panasonic2020_d

前提知識

• 枝刈り全探索 （ちょっと違う気もするけど、感覚は似ている）

解説

https://atcoder.jp/contests/panasonic2020/submissions/10896021

問題の定義が少し複雑に感じるかもしれない。
こういうときは、つまりこういうことができればいいというのを考えるといい。
操作が複雑な問題とか、条件が多い問題とか、そういう問題でもこういう方針から入る。

今回は頑張って例を出しながら考えていくと、
先頭から文字を追加していくが「追加するのに使えるのは'a'～今まで使われた文字の次の文字」というのを満たす文字列の全列挙である。
例を出すと、最初はaだけOK。
2つ目は、今までaが出ているので、aから次のbまで使える。よって、aaとab。
aaに追加する3つ目は、今までaが出ているので、aから次のbまで使えるので、aaaとaab。
abに追加する3つ目は、今までabが出ているので、aから次のcまで使えるので、aba, abb, abcとなる。
これを繰り返していく。

これを全部列挙すると、O(N!)通りになる。
これは1つ目は最大1択で、2つ目は最大2択で、3つ目は最大3択で、全部最大として考えるとN!通りとなるためである（実際はそれより少ない）。
10!は3*10⁶くらいで、実際はそれより少ないので、まあ行けるんじゃないかなーと思える。

後は、実装であるが、先頭から順番に決めていくのでdfsを使う。
dfsを使って重複順列を全列挙したことがある人は、感覚がつかめるだろう。
そっちで感覚をつかんだほうが、こちらに導入しやすいかもしれない。

dfsでは毎回最大の文字を求めて、'a'から最大+1までを後ろに追加する操作を繰り返していく。

int N;
//---------------------------------------------------------------------------------------------------
string buf = "";
void dfs(int cu) {
    if (cu == N) {
        printf("%s\n", buf.c_str());
        return;
    }

    char biggest = 'a';
    while (buf.find(biggest) != string::npos) biggest++;
    biggest--;

    for (char c = 'a'; c <= biggest + 1; c++) {
        buf.push_back(c);
        dfs(cu + 1);
        buf.pop_back();
    }
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;

    dfs(0);
}