D - String Equivalence

解説とやり方少し違ったから一応書くけど、多分解説のやり方でいいと思う

考察

思いつかない時はとりあえず軽く実験をするべき
今回のはN=3くらいなら手でも書けるレベルなので書く
1文字目必ずaじゃんそれはそう〜みたいな気持ちになる
で、標準形では同じ種類の文字の入る場所が重要な訳で、1文字目にaを入れた時に残りのaが入る箇所も一緒に確定させられるなぁとなる

具体例を出すと、N=4の時にaの入る箇所だけ注目すれば
a###
a##a
a#a#
a#aa
aa##
aa#a
aaa#
aaaa
の8種類に分類できるよねということ（#にはb以降が入る）
で、それぞれについて
・#が含まれない場合 : 出力する文字列の一つなので出力setに追加
・#が含まれる場合 : #をb以降の文字で同様に埋める

コード

#include <bits/stdc++.h>
using namespace std;

int n;
vector<string> ans;

void dfs(string s,char c){
  vector<int> v;
  for(int i=0;i<n;i++)if(s[i]=='#')v.push_back(i);
  int A=v.size();
  if(!A)ans.push_back(s);
  else{
    s[v[0]]=c;
    for(int i=0;i<(1<<A-1);i++){
      string t=s;
      for(int j=0;j<A-1;j++)if((i>>j)&1)t[v[j+1]]=c;
      dfs(t,c+1);
    }
  }
}

int main(){
  dfs(string((cin>>n,n),'#'),'a');
  sort(ans.begin(),ans.end());
  for(string p:ans)cout<<p<<endl;
}

提出

Submission #10922686 - Panasonic Programming Contest 2020