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

D - String Equivalence

公式解説と別の方法でACしたので共有します。DFSによる全探索は様々な方法で実装できます。いろいろな実装方針で書けるようになると、何が本質なのかが見えてきやすくなり、問題によらずAC率が上がると思うので、ぜひ一度通したことがある人でも読んでくださると嬉しいです。

問題概要

文字列の形に関する問題。長さNで、ある形の標準形（辞書順最小）を全て出力せよ。

解説

単純に長さNの文字列を全探索すると26^Nある。 一方で標準形を全て試すだけならN種類の文字列で事足りる。 つまり今回の問題で言えばN^Nを全探索すればよい。DFSで実装できそうである。 しかし10¹⁰はTLEしてしまうのでどうにかしたい。ここで、メモ化再帰の出番である。 今回必要な標準形は、辞書順最小なので、例えば最初の文字がaのもの以外は必要ない。bとかcはそのあとの文字をつなげる必要がないのである。 ある形があったときに、その辞書順最小は前から貪欲に小さい文字を置いていけば構築できる。 aaabとaaacだったらaaabだけあれば良いし、xxxxxyxxzだったらaaaaabaacとすれば良い。 つまり探索途中で形だけに注目し、その形が既出だったらそれ以上の探索を打ち切ることができる。 これがメモ化再帰で実現可能。 計算量はO(N!)に結果的に落ちる。

実装

#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)

int N;
string henkan(string s){
    //今まで出てきた文字数を確認する
    map<char, int> chars;
    map<char, char> char2char;
    string res = "";
    rep(i,s.size()){
        if(chars[s[i]] == 0){
            char bck = char('a' + chars.size()-1);
            res.push_back(bck);
            chars[s[i]]++;
            char2char[s[i]] = bck;
        }
        else{
            res.push_back(char2char[s[i]]);
        }
    }
    return res;
}
map<string, int> maps;
set<string> ans;
void dfs(string s){
    string x = henkan(s);
    if(maps[x])return;
    maps[x]++;
    if((int)x.size() == N){
        ans.insert(x);
        return;
    }
    for(int i = 0; i < N;i++){
        string nx = x;
        nx.push_back(char(i + 'a'));
        dfs(nx);
    }
}
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    cin >> N;
    dfs("");
    for(auto y:ans){
        cout << y << endl;
    }
}

提出