Codeforces Round #659 (Div. 2) A번 풀이

이번에 드디어 green을 달았다. 아마 다음 코포 때는 민트를 찍지 않을까 싶다.

이번 코포는 난이도 분배가 최악이였다.. 차라리 B말고 C를 건드렸으면 더 나았을 것 같다.
결국 A번만 솔브하고 1시간 40분 동안 뭐했는지 모르겠다.

A번을 간략히 설명하자면..
Ai = 문자열 Si과 Si+1의 앞 부분의 가장 긴 공통 길이
으로 둘 때, 입력되는 Ai에 대한 Si와 Si+1을 출력하는 문제이다.

Ai의 최댓값을 size로 하는 임의의 string을 구성해야 한다.

아래와 같은 테스트 케이스가 있다고 가정하자.
1 5 3
이 경우 Ai의 최댓값은 5가 된다.
임의의 string을 aaaaa라고 두자.

그러면, 첫번째 string은 aaaaa가 된다.
두번째 string은 1개가 겹쳐야 하므로, 2번째부터 5번째까지의 문자열을 바꿔준다. (필자의 경우 1씩 더해줬다.)
그러면 두번째 string은 abbbb가 된다.

5개가 겹치는 경우는 그대로 출력하면 된다.
따라서 세번째 string도 abbbb가 된다.

마지막으로 3개가 겹치면 4번째부터 5번째의 string을 바꿔주면 된다.
네번째 string은 abbcc가 된다.

이런 식으로 코드를 짜면 된다.

글을 적고 보니 굳이 뒷 문자열을 다 더해주지 말고, Ai + 1번째 문자 하나만 바꿔줘도 될 것 같다.

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cout.tie(0);
 
	int T;
	cin >> T;
	while (T--) {
		int n;
		cin >> n;
 
		string prev = "";
		vector<int> l;
		int size = 1;
		for (int i = 0; i < n; i++) {
			int a; cin >> a;
			size = max(size, a);
			l.push_back(a);
		}
 
		prev.assign(size, 'a');
		cout << prev << "\n";
		for (const int &a : l) {
			for (int i = a; i < size; i++) prev[i] = prev[i] == 'z' ? 'a' : prev[i] + 1;
			cout << prev << "\n";
		}
	}
}