PANASONIC_2020_D - String Equivalence

[zeikar]

Problem link

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

Problem Summary

n 길이의 isomorphic 한 normal form를 전부 구하는 문제

Solution

예시에 2밖에 없어서 뭔가 애매한데 4 예시를 직접 만들어보자.

aaaa
aaab
aaba
aabb
aabc
abaa
abab
abac
abba
abbb
abbc
abca
abcb
abcc
abcd

총 15개가 나오고 규칙을 찾을 수 있다.

s[i] 뒤에는 s[0 ... i] + 1 이하의 알파벳이 와야 한다.

좀더 formal하게는

이건 재귀적으로 간단하게 짤 수 있다.

Source Code

#include <iostream>
#include <string>
using namespace std;

int n;

void solve(string s, int prevMax) {
	if (s.length() == n)
	{
		cout << s << endl;
		return;
	}

	for (int i = 0; i <= prevMax + 1; i++)
	{
		solve(s + (char)('a' + i), max(prevMax, i));
	}
}

int main() {
	cin >> n;

	solve("", -1);
}