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

D - String Equivalence

問題概要

abcacなどの標準形を探す問題

制約

1<=N<=10
入力はすべて整数

考えたこと

再帰関数問題だということは分かっていた。まず文字コードで書く場合を考えたが、それよりも楽で簡単な方法があることに気が付いた。
それが//cout << ("b" - "a"); => 4である。これは、(c - a, d - a, e - a)とすると{4,8,12...}と続いていくため、４で割ってあげてindexにすればよい。
だが、途中でエラーが起きた。原因はchar型によるミス。char 型だと{1,2,3..}と続くらしい（//cout << ('b' - 'a'); => 1）めんどくさい。そこを直した。

また、

//文字列は必ずaから始まる
//文字列のz向きのつながりは2つ以上飛ばしにはならない。(ac..)はあり得ない。
//(a,b,c,d..)と来た時、5つ目にはa,b,c,d,eのいずれかが入れる。for使おう。
//(a,b,a,c)も成立する。forで(a,b,a)の中からbを抜き出し、cを入れる

等の条件を絞り出していった。
３つ目までは簡単にできていたが4つ目は少し苦戦した。これは気付かない。

こーど

int N;
vector<string>ABC = { "a","b","c","d","e","f","g","h","i","j" };
vector<string>Data;

void dfs(string W) {

	if (W.size() == N) {
		Data.push_back(W);
		return;
	}

	//<a,b,c,d..>と来た時、5つ目にはa,b,c,d,eのいずれかが入れる。
	//<a,b,a,c>も成立する。forで<a,b,a>の中からbを抜き出し、cを入れる
	int i_end = 0;
	for (char str : W) {
		if (str - 'a' > i_end) {
			i_end = str - 'a';
		}
	}

	for (int i = 0; i < i_end + 2; i++) {
		W += ABC[i];
		dfs(W);
		W.pop_back();
	}

}

int main() {

	cin >> N;//1<<N<<10
	string W = "a";
	dfs(W);

	for (string str : Data) {
		cout << str << endl;
	}
}

//文字列は必ずaから始まる
//文字列のz向きのつながりは2つ以上飛ばしにはならない。<ac..>はあり得ない。
//<a,b,c,d..>と来た時、5つ目にはa,b,c,d,eのいずれかが入れる。for使おう。
//<a,b,a,c>も成立する。forで<a,b,a>の中からbを抜き出し、cを入れる

//str = "" に += a,b..をしていく。
//97	0x61	a
//98	0x62	b
//99	0x63	c
//100	0x64	d
//101	0x65	e
//102	0x66	f
//103	0x67	g
//104	0x68	h
//105	0x69	i
//106	0x6a	j
//107	0x6b	k

//cout << ("d" - "a") / 4;//これでindexが得られる。

//cout << ("b" - "a"); => 4
//cout << ('b' - 'a'); => 1

楽しかった。ほかの人のコードを見る必要がないと判断したため載せない。