본문 바로가기
Algorithm/Codeforces

Educational Codeforces Round 127 (Rated for Div. 2)

이유섭 2022. 4. 23. 03:46

Problems
Submissions
Standing
Rating

 

 

A. String Building

Problem

https://codeforces.com/contest/1671/problem/A

 

https://codeforces.com/contest/1671/problem/A

 

codeforces.com

 문자열 s가 주어진다. 너는 문자열 aa, aaa, bb, bbb를 이어서 주어진 문자열 s를 만들 수 있는지 없는지를 알아내야 한다. 문자열 aa, aaa, bb, bbb는 여러 번 쓸 수 있으며, 어떠한 순서로도 사용할 수 있다.

 

 예를 들어:

  • aaaabbb는 aa+aa+bbb로 만들 수 있고
  • bbaaaaabbb는 bb+aaa+aa+bbb로 만들 수 있고
  • aaaaaa는 aa+aa+aa로 만들 수 있지만
  • abab는 aa, aaa, bb, bbb로 만들 수 없다.

 

 

Input

 첫째 줄에는 테스트 케이스의 개수를 의미하는 하나의 정수 t($1 \le t \le 1000$)가 주어진다.

 

 각 테스트 케이스에서는 문자 a와 b로 이루어진 문자열 s($1 \le |s| \le 50$)가 주어진다.

 

 

Output

 각각의 테스트 케이스에 대하여 문자열 s를 만들 수 있으면 YES를 출력하고 그렇지 않으면 NO를 출력하여라.

 

 

Example

input output
8
aaaabbb
bbaaaaabbb
aaaaaa
abab
a
b
aaaab
bbaaa		 YES
YES
YES
NO
NO
NO
NO
YES

 

Note

 예제에서 앞의 4개의 테스트 케이스는 본문에서 설명하였다.

 

Tutorial

 2와 3으로는 1을 제외한 모든 양의 정수를 만들 수 있다. 즉, a와 b가 연속해서 하나만 나오는 문자열을 제외하고 모든 문자열을 만들 수 있다.

 

 a와 b가 중간에 연속해서 하나만 나오는지 아닌지는 단순히 카운트를 통해서 알아낼 수 있다.

 

Solution

#include <bits/stdc++.h>

using namespace std;

int main()
{
	int t, i, a, b;
	string s;
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	cin >> t;
	while(t--){
		cin >> s;
		
		a = b = 0;
		for(i=0; i<s.size(); i++){
			if(s[i] == 'a'){
				if(b == 1) break;
				a++;
				b = 0;
			}
			if(s[i] == 'b'){
				if(a == 1) break;
				b++;
				a = 0;
			}
		}
		
		if(a == 1 || b == 1) cout << "NO\n";
		else cout << "YES\n";
	}
	
	return 0;
}

 

 

B. Consecutive Points Segment

Problem

https://codeforces.com/contest/1671/problem/B

 

https://codeforces.com/contest/1671/problem/B

 

codeforces.com

 수직선 위의 정수 좌표를 가지는 n개의 점이 주어진다. i번째 점의 좌표는 $x_i$이다. 모든 점은 중복되지 않으며, 증가하는 순서로 주어진다.

 

 각 점들 i에 대하여, 너는 다음의 작업을 최대 한번 할 수 있다: 이 점을 왼쪽 혹은 오른쪽으로 1만큼 움직이다(즉, $x_i$좌표를 $x_i-1$ 혹은 $x_i+1$로 바꾼다). 다시 말해, 각 점들에 대해, 너는 (각각) 새로운 좌표를 고를 수 있다. i번째 점은 $x_i-1$이나 $x_i$, $x_i+1$이 될 수 있다.

 

 너가 해야 할 일은 너가 몇몇 점들을 옮겨 점들을 연속적으로 배치할 수 있는지를 판단하는 것이다. 즉, 어떠한 l에 대하여 점들의 좌표를 l, l+1, ..., l+n-1로 만들 수 있는지 판단하여라.

 

 최종 점들은 서로 다른 좌표를 가져야 함에 유의하여라.

 

 너는 t개의 독립적인 테스트 케이스에 대하여 답해야 한다.

 

 

Input

 첫째 줄에는 테스트 케이스의 개수를 의미하는 하나의 정수 t($1 \le t \le 2 \cdot 10^4$)가 주어진다.

 

 각 테스트 케이스의 첫째 줄에는 점들의 개수를 의미하는 하나의 정수 n($1 \le n \le 2 \cdot 10^5$)이 주어진다.

 

 각 테스트 케이스의 둘째 줄에는 n개의 정수 $x_1 < x_2 < ... < x_n (1 \le x_i \le 10^6)$이 주어지며, $x_i$는 i번째 점의 좌표를 의미한다.

 

 점들은 정확히 증가하는 순서(이것은 모든 좌표가 중복되지 않는다는 것도 의미한다)로 주어진다는 것이 보장된다. 또한 n들의 합이 $2 \cdot 10^5 (\sum n \le 2 \cdot 10^5)$을 넘지 않음이 보장된다.

 

 

Output

 각각의 테스트 케이스에 대하여 점들을 옮겨 연속된 수열로 만들 수 있다면 YES를, 그렇지 않으면 NO를 출력하여라.

 

 

Example

input output
5
2
1 4
3
1 2 3
4
1 2 3 7
1
1000000
3
2 5 6		 YES
YES
NO
YES
YES

 

 

Tutorial

 $x_1$을 $x_1-1$로 옮겨야만 가능한 경우는 없다. 또한 $x_1$을 옮기지 않고 답이 되는 경우는 $x_1$을 오른쪽으로 옮겨도 답을 만들 수 있다. 즉, $l$을 $x_1+1$로 설정한 후, i번째 점을 $l+i-1$로 만들 수 있는지 확인하여 문제를 해결할 수 있다.

 

 + 풀이를 적으면서 생각났는데, 중복되지 않으며 오름차순으로 주어진다고 하였으므로, $x_n - x_1 \le 2$이면 YES라고 할 수 있을 것 같다.

 

 

Solution

#include <bits/stdc++.h>

#define MAXN 200010

using namespace std;

int x[MAXN];

int main()
{
	int t, n, i, l;
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	cin >> t;
	while(t--){
		cin >> n;
		
		for(i=0; i<n; i++) cin >> x[i];
		
		l = x[0]+1;
		for(i=1; i<n; i++){
			if(l+i == x[i]-1) continue;
			if(l+i == x[i]) continue;
			if(l+i == x[i]+1) continue;
			break;
		}
		
		if(i<n) cout << "NO\n";
		else cout << "YES\n";
	}
	
	return 0;
}

 

 

C. Dolce Vita

Problem

https://codeforces.com/contest/1671/problem/C

 

https://codeforces.com/contest/1671/problem/C

 

codeforces.com

 격동의 시기가 다가오고 있다. 이에 너는 설탕을 사기로 결심했다. 주위에 설탕을 파는 매점이 n군데 있다: i번째 매점은 한팩의 설탕을 $a_i$원에 판다, 그러나 하루에 한 고객에게 한팩만 판다. 그래서 여러 팩을 사기 위해서는 여러 매점을 방문해야 한다.

 

 또 다른 문제는 매일 가격이 오른다는 것이다: 첫째 날에는 가격이 $a_i$이지만, 둘째 날에는 가격이 $a_i + 1$이고, 셋째 날에는 가격이 $a_i+2$이며, 다른 날도 이와 같이 오른다.

 

 이와는 반대로, 너의 하루 예산은 오직 x원이다. 다시 말해, 각각의 날에 너는 총비용이 x원이 넘지 않으면서 가능한 많은 팩을 사려고 한다. 너가 돈을 다 쓰지 못했다고 해서 이 돈을 다음날 쓸 수 있는 것은 아니라는 것을 명심하자.

 

 결국, 모든 팩들의 가격이 x를 넘어서고, 너는 한팩도 사지 못할 것이다. 그 순간이 오기전까지 너가 얼마나 많은 팩을 살 수 있는가?

 

 

Input

 첫째 줄에는 테스트 케이스의 개수를 의마하는 하나의 정수 t($1 \le t \le 1000$)이 주어진다. 다음으로 t개의 테스트 케이스가 주어진다.

 

 각 테스트 케이스의 첫째 줄에는 매점의 수와 하루 예산을 의미하는 2개의 정수 n과 x($1 \le n \le 2 \cdot 10^5; 1 \le x \le 10^9$)가 주어진다.

 

 각 테스트 케이스의 둘째 줄에는 각 매점의 한팩의 초기 가격을 의미하는 n개의 정수 $a_1, a_2, ..., a_n (1 \le a_i \le 10^9)$이 주어진다.

 

 n의 총 합은 $2 \cdot 10^5$을 넘지 않음이 보장된다.

 

 

Output

 각각의 테스트 케이스에 대하여, 가격들이 너의 하루 예산을 넘기기 전까지 너가 살 수 있는 팩의 총개수를 의미하는 하나의 정수를 출력하여라.

 

 

Example

input output
4
3 7
2 1 2
5 9
10 20 30 40 50
1 1
1
2 1000
1 1		 11
0
1
1500

 

Note

 첫번째 테스트 케이스에서,

  • Day 1: 가격은 [2, 1, 2]이다. 너는 3개의 팩 모두 살 수 있다, $2 + 1 + 2 \le 7$이기 때문에.
  • Day 2: 가격은 [3, 2, 3]이다. 너는 3개의 팩 모두 살 순 없다. $3 + 2 + 3 > 7$이기 때문에, 그래서 너는 2개의 팩만 사야 한다.
  • Day 3: 가격은 [4, 3, 4]이다. 너는 가격이 4와 3인 2개의 팩을 살 수 있다.
  • Day 4: 가격은 [5, 4, 5]이다. 너는 더 이상 2개의 팩을 살 수 없다. 따라서 너는 오직 한 개의 팩만 사야 한다.
  • Day 5: 가격은 [6, 5, 6]이다. 너는 1개의 팩을 살 수 있다.
  • Day 6: 가격은 [7, 6, 7]이다. 너는 1개의 팩을 살 수 있다.
  • Day 7: 가격은 [8, 7, 8]이다. 너는 아직 가격이 7인 팩을 한 개 살 수 있다.
  • Day 8: 가격은 [9, 8, 9]이다. 가격이 너무 높아 너는 더 이상 아무것도 살 수 없다.

 

 총 합해서 너는 3 + 2 + 2 + 1 + 1 + 1 + 1 = 11개의 팩을 살 수 있다.

 

 두 번째 테스트 케이스에서는 첫날부터 가격이 너무 높아 너는 아무것도 살 수 없다.

 

 세 번째 테스트 케이스에서, 너는 오직 한 날에 하나의 팩만 살 수 있다.

 

 네 번째 테스트 케이스에서, 너는 첫 500일 동안 2개의 팩을 살 수 있다. 501일에는 가격이 [501, 501]이라서 다음 500일 동안은 한팩 밖에 살 수 없다. 1001일에는 가격이 [1001, 1001]이라서 아무것도 살 수 없다. 총 합해서 너는 $500 \cdot 2 + 500 \cdot 1 = 1500$개의 팩을 살 수 있다.

 

 

Tutorial

 우선 가격이 싼 순으로 사는 것이 이득이므로 입력으로 받은 가격을 정렬해준다. (후술 되는 $a_i$들은 정렬 후의 $a_i$를 의미한다.)

 

 날짜를 기준으로 하루에 살 수 있는 팩의 개수를 새기에는 무리가 있어 보인다. 따라서 각 매점에서 언제까지 설탕을 구매할 수 있는지를 구할 것이다. 첫 번째 매점은 매일 맨 처음 들릴 것이기 때문에 $x - a_i + 1$팩만큼 살 수 있을 것이다. 다음으로 두 번째 매점은 첫 번째 매점 방문 후, 두 번째로 들르기 때문에 첫날에는 $a_1 + a_2$원이 있어야 들르고, 둘째 날에는 $a_1 + a_2 + 2$원이 있어야 들르고,..., k번째 날에는 $a_1 + a_2 + 2(k-1)$원이 있어야 들를 것이다. 즉, $a_1 + a_2 + 2(k-1) \le x$인 최대 k를 구해주면 $k = \lfloor (x - (a_1 + a_2)) / 2 \rfloor + 1$이 된다. 즉, $a_1$부터 $a_i$까지의 합을 $sum_i$라고 한다면, i번째 매점에서는 $\lfloor (x - sum_i) / 2 \rfloor + 1$만큼의 팩을 사게 된다.

 

 계산 과정에서 int 범위를 벗어날 수 있다는 것과, $sum_i$가 x보다 클 수 있다는 것에 주의하자.

 

 

Solution

#include <bits/stdc++.h>

using namespace std;

int a[200010];

int main()
{
	int t, n, i;
	long long x, sum, ans;
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	cin >> t;
	while(t--){
		cin >> n >> x;
		for(i=0; i<n; i++) cin >> a[i];
		
		sort(a, a+n);
		
		sum = ans = 0;
		for(i=0; i<n; i++){
			sum += a[i];
			
			if(sum <= x) ans += (x-sum) / (i+1) + 1;
		}
		
		cout << ans << '\n';
	}
	
	return 0;
}

 

 

D. Insert a Progression

Problem

https://codeforces.com/contest/1671/problem/D

 

Problem - D - Codeforces

 

codeforces.com

 n개의 정수 수열 $a_1, a_2, ..., a_n$이 주어진다. 또한 x개의 정수 1, 2, ..., x가 주어진다.

 

 너는 수열 a에 추가로 주어진 정수를 집어넣는 요청을 받았다. 각각의 정수는 수열의 처음과, 끝, 중간 어디든 들어갈 수 있다.

 

 최종 수열 $a'$의 점수는 인접한 원소들의 차이의 합이다. ($\sum_{i=1}^{n+x-1} |a'_i - a'_{i+1}|$)

 

 $a'$의 가장 작은 점수는 얼마인가?

 

 

Input

 첫째 줄에는 테스트 케이스의 개수를 의미하는 하나의 정수 t($1 \le t \le 10^4$)이 주어진다.

 

 각 테스트 케이스의 첫째 줄에는 수열의 길이와 추가되는 정수의 개수를 의미하는 두 개의 정수 n과 x($1 \le n, x \le 2 \cdot 10^5$)가 주어진다.

 

 각 테스트 케이스의 둘째 줄에는 n개의 정수 $a_1, a_2, ..., a_n (1 \le a_i \le 2 \cdot 10^5)$이 주어진다.

 

 모든 테스트 케이스에 대하여 n의 합은 $2 \cdot 10^5$을 넘지 않음이 보장된다.

 

 

Output

 각 테스트 케이스에 대하여, 추가되는 정수들을 넣은 수열에서 인접한 원소들의 차의 합 중 가장 작은 값을 의미하는 하나의 정수를 출력하여라.

 

 

Example

input output
4
1 5
10
3 8
7 2 10
10 2
6 1 5 7 3 3 9 10 10 1
4 10
1 3 1 2		 9
15
31
13

 

Note

 다음은 예제에 대한 가장 작은 점수를 가진 수열들이다. 밑줄 친 원소들이 추가된 정수들이다. 가장 작은 점수를 가지는 다른 수열들도 존재함에 주의하여라.

  • 1, 2, 3, 4, 5, 10
  • 7, 7, 6, 4, 2, 2, 1, 3, 5, 8, 10
  • 6, 1, 1, 2, 5, 7, 3, 3, 9, 10, 10, 1
  • 1, 3, 1, 1, 2, 2, 3, 4, 5, 6, 7, 8, 9, 10

 

Tutorial

 절댓값의 특성상 $a_l, a_{l+1}, ..., a_r$이 오름차순 혹은 내림차순이라면, $\sum_{i=l}^{r-1} |a_i - a_{i+1}| = |a_r - a_l|$임을 알 수 있다. 즉, 우리는 $a_i$와 $a_{i+1}$ 사이에 값이 $a_i$와 $a_{i+1}$ 사이인 추가 정수를 넣어 점수 변화 없이 추가 정수들을 수열에 넣을 수 있다.

 

  이러한 방법을 사용하면 우리는 $min(a_i)$부터 $max(a_i)$사이의 값을 갖는 추가 정수들을 점수 변화 없이 처리할 수 있다. 문제는 1부터 $min(a_i)-1$까지의 수와, $max(a_i)+1$부터 x까지의 수이다($min(a_i)$와 $max(a_i)$의 값에 따라 남는 수가 없을 수도 있다). 이들은 수열의 맨 앞 혹은 맨 뒤에 붙이거나 $a_i$의 최솟값 혹은 최댓값 뒤에 붙임으로써 점수를 최소화할 수 있다. 수열의 맨 앞 혹은 맨 뒤에 붙일 경우, $a_1-1, x-a_1, a_n-1, x-a_n$ 중 하나의 점수가 추가될 것이며, $a_i$의 최솟값 혹은 최댓값 뒤에 붙일 경우, $2 \times (min(a_i) - 1), 2 \times (x - max(a_i))$ 중 하나의 점수가 추가가 될 것이다.

 

 x가 $max(a_i)$보다 작은 경우 처리에 주의하자.

 

 

Solution

#include <bits/stdc++.h>

#define MAXN 200010
#define MAX 200000

using namespace std;

int a[MAXN];

int main()
{
	int t, n, x, i, mini, maxi;
	long long ans;
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	cin >> t;
	while(t--){
		cin >> n >> x;
		
		mini = MAX;
		maxi = 0;
		ans = 0;
		for(i=0; i<n; i++){
			cin >> a[i];
			
			mini = min(mini, a[i]);
			maxi = max(maxi, a[i]);
			
			if(i) ans += abs(a[i]-a[i-1]);
		}
		
		ans = min(ans+a[0]-1, min(ans+a[n-1]-1, ans+(mini-1)*2));
		x = max(maxi, x);
		ans = min(ans+x-a[0], min(ans+x-a[n-1], ans+(x-maxi)*2));
		
		cout << ans << '\n';
	}
	
	return 0;
}

 

 

E. Preorder

Problem

 

https://codeforces.com/contest/1671/problem/E

 

Problem - E - Codeforces

 

codeforces.com

 $2^n - 1$개의 정점을 가진 루트 트리가 주어진다. 각 정점은 0개 혹은 2개의 자식을 같는다. 트리의 모든 말단은 루트로부터 같은 길이를 가지며, 모든 중간 정점은 하나의 왼쪽 자식과 하나의 오른쪽 자식을 같는다. 즉, 완전 이진트리가 주어진다.

 

 트리의 정점은 다음의 순서로 번호가 붙는다:

  • 루트의 인덱스는 1이다
  • 어떤 정점의 인덱스가 x라면, 그 정점의 왼쪽 자식의 인덱스는 2x, 오른쪽 자식의 인덱스는 2x+1이다.

 

 트리의 모든 정점에는 A와 B 중 하나의 알파벳이 쓰여 있다. 정점 x의 문자를 $s_x$라고 정의하자.

 

 어떤 정점 x의 전위 문자열을 다음과 같이 정의하자:

  • 만약 정점 x가 말단이라면, x의 전위 문자열은 오직 하나의 문자 $s_x$로 이루어져 있다.
  • 그렇지 않다면, x의 전위 문자열은 $s_x + f(l_x) + f(r_x)$이다. + 연산은 문자열의 연결을 의미한다. $f(l_x)$는 x의 왼쪽 자식의 전위 문자열이고, $f(r_x)$는 x의 오른쪽 자식의 전위 문자열이다.

 

 트리의 전위 문자열은 루트의 전위 문자열이다.

 

 자, 문제는...

 

 전위 문자열을 만들기 전에 너에게 다음 작업을 얼마든지 할 수 있도록 한다면, 얻을 수 있는 서로 다른 전위 문자열의 개수를 구하여라:

  •  중간 정점 x를 고른 후, 그것의 자식을 바꿔라(즉, 왼쪽 자식과 오른쪽 자식이 서로 바뀐다).

 

 

Input

 첫째 줄에는 하나의 정수 n($2 \le n \le 18$)이 주어진다.

 

 둘째 줄에는 $2^n-1$개의 문자 $s_1, s_2, ..., s_{2^n-1}$이 주어진다. 각각의 문자는 A 혹은 B이다. 문자들은 공백이나 다른 것들로 나눠져 있지 않다.

 

 

Output

 여러 번의 작업이 가능할 때, 주어진 트리에서 얻을 수 있는 서로 다른 전위 문자열의 개수를 의미하는 하나의 정수를 출력하여라. 이 값은 매우 클 수 있기 때문에, 998244353으로 나눈 나머지를 출력하여라.

 

 

Example

input output
4
BAAAAAAAABBABAB		 16
2
BAA		 1
2
ABA		 2
2
AAB		 2
2
AAA		 1

 

 

Tutorial

 이 풀이는 검증되지 않은 풀이입니다.

 + Educational Codeforces Round 127 (Rated for Div. 2) - E 글에서 풀이를 확인할 수 있습니다.

 

 문제에선 거창하게 전위 문자열의 개수를 구하라고 하였지만, 결국 서로 다른 트리를 구하라는 문제와 동일하다. dp[i]를 "i 정점을 루트로 하는 서브 트리가 가질 수 있는 서로 다른 트리의 개수(경우의 수)"라고 정의해보자. 그러면 중학교 확통 시간에 배웠던 대로 자식을 바꾸지 않으면 "$dp[i] = dp[l] \times dp[r]$"이라고 쓸 수 있을 것이다. 또한 자식을 서로 바꿀 수 있으므로 "$dp[i] = 2 \times dp[l] \times dp[r]$"이 된다. (사실 돌아 돌아 생각하느라 여기까지 생각하는데도 꽤 오랜 시간이 걸렸다 ㅜㅜ)

 

 그러나 $\times 2$가 항상 되는 것은 아니다. 바로 왼쪽 서브 트리와 오른쪽 서브 트리가 같은 경우이다. 여기서 말하는 같다는 의미는 변환 작업을 통해 각각의 서브 트리를 사전순으로 가장 작게 했을 때의 트리가 같음을 의미한다(이게 같은 경우에만 중복되는 경우가 있다는 것을 알아내는데 시간이 오래 걸렸다).

 그러나 크기가 최대 $2^{18}$이나 될지도 모르는 서브트리를 일일이 다 확인할 수가 없다. 처음에는 아무 생각 없이 트리의 정보를 비트로 나타내서 가지고 있으면 되겠다 싶었지만 그러면 $2^{18}$비트 즉, $2^{2^{18}}$이 필요하다. 그래서 내가 생각해낸 방법은 바로 해시를 이용하자는 것이었다(ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ). 앞서 말했듯이 $2^{2^{18}}$를 담을 변수가 없기 때문에 이를 해시값을 이용해 빠르게 비교하는 것이다. 그러나 이렇게 해도 문제가 발생한다. 앞서 두 서브 트리가 같다는 것은 두 서브 트리의 사전 순으로 가장 작은 트리가 같음을 의미한다고 했기 때문에 두 트리의 대소 비교도 가능해야 한다. 여기서 또 내가 생각한 방법은 LCA를 구하는 방법과 비슷하게 한 칸 내려갔을 때 트리의 정보 두 칸 내려갔을 때 트리의 정보, .... 를 저장하고, 형제들에 대한 정보도 2의 거듭제곱만큼의 형제 정보를 저장하는 것이었다. 이렇게 하면 해시 값이 같을 때까지 내려가 보고  다른 순간 다른 곳의 위치를 빠르게 찾아 두 트리를 비교할 수 있을 것이라고 생각하였다.

 

 이상 매우 해괴한 풀이였다. 이것을 생각해 냈을 때가 20분 정도 남았을 때였는데, PS에서 해시를 다뤄보지도 않았고, 이렇게 해괴망측한 풀이를 코드로 옮긴다면 코드도 해괴망측할 것이라 생각하여 10분 정도 더 고민한 후 대회를 마쳤다 ㅎㅎ...

 

 

마치며...

 D번까지 30분도 안되어 후다닥 풀어 "어? 내가 진짜 실력이 늘었나?"라고 잠깐 생각을 하였지만, 이전에도 Educational Codeforces 문제들이 쉬웠다는 것을 깨닫고 이내 레이팅을 올리기 위해 E에 집중을 하였다. 그러나 위의 풀이를 읽어보면 알겠지만 해괴망측한 풀이 밖에 떠오르지 않아 D번까지 풀며 대회를 마무리했다.

 

 그러나 비록 E를 풀지도 못했고, 언뜻 해괴망측해 보일 수도 있지만, 나름 좋은 발상이라고 생각했다. 단순히 같은지만을 비교해야 하는 문제에서 해시를 이용하면 정확도는 장담할 수 없지만 O(N)의 시간 복잡도를 O(1)로 줄이는 획기적인 방법이 아닐까라는 생각을 하였다. 이에 꼭 E를 풀기 위해서가 아니더라도 해시를 이용하여 두 트리를 비교하는 코드를 짜 보고 싶다는 생각이 들었다. (언젠간 이것도 해내서 포스팅해보도록 하겠다 ㅎㅎ)

'Algorithm > Codeforces' 카테고리의 다른 글

Codeforces Global Round 21  (0) 2022.06.27
Educational Codeforces Round 127 (Rated for Div. 2) - E  (0) 2022.04.27
Codeforces Round #783 (Div. 1)  (0) 2022.04.22
Codeforces Round #782 (Div. 2)  (0) 2022.04.19
Codeforces Round #781 (Div. 2) - D  (0) 2022.04.16

'Algorithm/Codeforces' Related Articles

티스토리툴바