Educational Codeforces Round 127 (Rated for Div. 2) - E

Submissions

 

 개인적으로 풀이 생각 과정과 AC를 받았을 때 희열을 느낀 문제 중 하나입니다.

 

 

E. Preorder

Problem

E. Preorder

Problem - E - Codeforces

 

 $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

 이전 글에서 생각한 풀이의 방향이 맞았다. 이전에 썼던 글을 일부 그대로 쓰겠다.

 

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

 

 그러나 $\times 2$가 항상 되는 것은 아니다. 바로 왼쪽 서브 트리와 오른쪽 서브 트리가 같은 경우이다. 여기서 말하는 같다는 의미는 변환 작업을 통해 각각의 서브 트리를 사전순으로 가장 작게 했을 때의 트리가 같음을 의미한다. 따라서 우리는 왼쪽 서브 트리와 오른쪽 서브 트리가 같은지를 효율적인 시간 안에 알아낸다면 쉽게 답을 구할 수 있다.

 

 문제는 두 서브 트리가 같은지를 어떻게 판단하냐는 것이다. 단순히 모든 문자열을 비교한다면 비교하는데만 $O(2^n)$ 만큼의 시간이 걸리게 된다. 이를 해결하기 위해서 이전 글에서 생각해낸 방법은 해시를 사용하는 것이었다. 해시 함수는 입력 문자열이 다르면 다른 해시 값을 반환하며, 해시값을 구하는데 O(1)의 시간이 걸리는 것으로 알려져 있다. 따라서 문자열 자체를 저장하는 것이 아닌 해시 값을 저장한다면 빠른 시간 안에 두 서브 트리를 비교해줄 수 있다.

 

 노드 p의 해시 값을 구하는 과정은 다음과 같다. 왼쪽 서브 트리의 해시 문자열을 l, 오른쪽 서브 트리의 해시 문자열을 r이라고 한다면, 노드 p의 해시 값은 hash(l + s[p] + r)로 구할 수 있다. 그러나 우리는 사실 두 서브트리가 완전히 같은지를 판단하는 것이 아니라 사전순으로 가장 작게 했을 때 트리가 같은지를 확인해야 한다. 이전 풀이에서는 이 부분을 해결하지 못해 헤맸다. 그러나 사실 사전순은 우리가 편의상 말했던 것이고, 트리를 일정하게 만들 수만 있다면 다른 방법을 써도 상관 없다. 따라서 이번에 생각한 방법은 해시 값을 기준으로 변환 작업을 하는 것이었다. 만약 오른쪽 서브트리의 해시 값이 더 작으면 노드 p의 해시 값을 hash(r + s[p] + l)로 하는 것이다. 그러면 트리의 형태를 일정하게 변환해 저장할 수 있게 된다.

 

 해시 함수는 hash<string> 을 사용하였다.

 

 

Solution

#include <bits/stdc++.h>

#define MAXN ((1<<18)+10)
#define MAX 998244353

using namespace std;

string s;
long long dp[MAXN];
size_t hs[MAXN];
hash<string> str_hash;

void dfs(int i, int n);

int main()
{
	int n;
	
	cin >> n;
	cin >> s;
	
	dfs(1, n);
	
	cout << dp[1];
	
	return 0;
}

void dfs(int i, int n)
{
	if(n == 1){
		dp[i] = 1;
		hs[i] = str_hash(to_string(s[i-1]));
		return;
	}
	
	dfs(i*2, n-1);
	dfs(i*2+1, n-1);
	
	if(hs[i*2] == hs[i*2+1]) dp[i] = dp[i*2]*dp[i*2];
	else dp[i] = dp[i*2]*dp[i*2+1]*2;
	dp[i] %= MAX;
	
	string l, r;
	if(hs[i*2] < hs[i*2+1]){
		l = to_string(hs[i*2]);
		r = to_string(hs[i*2+1]);
	}
	else{
		l = to_string(hs[i*2+1]);
		r = to_string(hs[i*2]);
	}
	
	hs[i] = str_hash(l + s[i-1] + r);
}

 

 

마치며...

 개인적으로 대회 이후 AC를 받았을 때 신기함에 웃음이 절로 나오는 문제였다. 해시를 사용한 방법을 떠올렸을 때엔 확률상 가능할거 같지만 너무 양아치 같은 풀이가 아닌가라는 생각이 들었고, 실제로 AC를 받았을 때는 이 풀이가 정말로 된다는 것에 놀랐다.

 

 이후 출제자가 의도한 풀이를 보니 놀랍게도 정말로 해싱을 하는 것이었다. 차이점이 있다면 나는 제공하는 해시 함수를 사용하였고, 출제자는 직접 해시를 정의한다는 것이었다. 그리고 사실 나는 확률에 기반하여 풀었지만 해시를 직접 만들면 해시값이 겹치지 않게 해시를 만들 수 있다는 사실을 알아 다시 한번 놀랐다.

 

 문제 자체를 봤을 땐 엄청 좋은 문제인지는 모르겠지만 암호학을 배웠던 나의 입장에서는 암호수학에서 배웠던 해시를 알고리즘에 적용할 수 있다는 점과 새로운 관점으로 문제를 바라볼 수 있다는 점에서 매우 매력적이고, 재미있는 문제라고 생각한다.