TakahiroNakamori

TakahiroNakamori

ナカモリタカヒロ

 
 

String Equivalence

問題

D – String Equivalence
プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…

記録

解法

  1. 文字列で使えるのはaから今まで使われた文字の次の文字。
  2. 1文字の場合はaしか使えない。
  3. 2文字の場合はaからbまで使えるので、aaab
  4. 3文字の場合はaからcまで使えるので、aaaaababaabbabcとなる。
  5. dfsで文字列を生成する。

コード例

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
// using mint = modint998244353;
// using mint = modint1000000007;
// const int mod = 1000000007;
// const ll INF = 1LL << 60;
// const int INF = 1001001001;

int N;

void dfs(string res, char mx) {
  int n = res.size();

  if(N == n) {
    cout << res << endl;
  } else {
    for(char c = 'a'; c <= mx; c++) {
      char v = mx;
      if(c == mx) {
        v = char(mx + 1);
      }
      dfs(res + c, v);
    }
  }
}

int main() {
  cin >> N;

  dfs("", 'a');
  return 0;
}