Codeforces Round #625 - D. Reachable Strings

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

Problem - D - Codeforces

두 문자열이 서로 연결되어있다(reachable)는 것을 다음과 같이 정의한다.

어떤 문자열에서 011 혹은 110 이 등장하면 그것을 각각 110, 011로 바꾸는 동작을 반복하면 다른 문자열과 같아질 수 있다.(원문 디스크립션 예시 참고 바람)

초기 문자열(S)이 주어지고 l, r, len 쿼리 형식으로 입력이 주어진다. S[l,l+1,...l+len-1]과 S[r,r+1,...r+len-1] 이 서로 reachable하면 Yes, 아니면 No를 출력하여라.

 

 

곰곰히 고민해보면 1이 두개 연속으로 있는 부분을 지워도 상관이 없다. 1이 달랑 한 개만 있으면 이동시킬 수가 없고, 두 개 붙어있다면 0이 좌우로 이동할 수 있으므로 없는 것으로 취급해도 괜찮기 때문이다. 이를 이용한 세그먼트 트리 솔루션이 있을 것 같은데, 아이디어를 떠올려도 코딩으로 구현하기 굉장히 어려워 보인다..

 

대회가 끝난 후 Radewoosh님이 댓글로 달았던 솔루션이 아주 인상깊었다. 해시를 돌파구로 사용한 해답이다. 처음 봤던 아주 유용한 방법인 것 같아서 개인 블로그에 기록할 예정이다.

 

 

부분 문자열을 해싱을 시킨다. 해시값은 정수에서 정수로 가는 함수이다.(??) '0'을 만나면 $f_0$ 함수를, '1'을 만나면 $f_1$ 함수를 적용하여 왼쪽에서 오른쪽으로 해시를 시킨다고 생각해보자. 즉, 부분 문자열 $S[l, l+1, l+2, ..., r]$에 대한 해시값은 $f_{S[l]} \circ f_{S[l+1]} \circ \cdots \circ f_{S[r]}$ 로 구간 합성함수 그 자체를 해시값으로 표현할 것이다.

 

여기서 만족해야할 조건은 $f_1 ( f_1 (x)) = x$를 만족해야한다는 것이다. 그래야지만 연속된 1을 무시하여 해시값을 계산한다.

 

이를 만족하는 간단한 함수는 다음과 같다. (단, $h_1, h_2, h_3, m$ 은 적당히 큰 소수)

$$f_0 (x) = h_1 x + h_2 \mod m$$

$$f_1(x) = h_3 - x \mod m$$

정말로 $f_1(f_1(x)) = x$가 성립한다. 이런 생각을 어떻게 했는지 모르겠다..

 

그런데 해시값을 함수로 정의하면 두 해시값이 서로 같은지 어떻게 판단하는가? 여기서 $f_0$과 $f_1$ 함수는 모두 선형함수이다. 이를 여러 번 합성해도 선형함수이다. 선형함수는 $f(x) = ax + b\mod m$ 꼴을 가지는데, 서로 다른 $x_1 \neq x_2$에 대해 $f(x_1)$, $f(x_2)$의 값이 있으면 함수의 구성요소인 $a$, $b$ 값을 알 수 있다. 이를 통해 두 선형함수가 서로 같은지 빠르게 판단할 수 있다.

 

 

아래 코드가 이를 구체적으로 설명한다고 생각한다.

 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define CPPIO ios::sync_with_stdio(0); cin.tie(0); cout << std::setprecision(10); cout << fixed

const ll MOD = 1e9 + 7;
const ll H1 = 100403, H2 = 142433, H3 = 185099;
const int MAX_N = 2e5 + 20;

int N;
char A[MAX_N];
ll H[MAX_N], U[MAX_N];

ll mod_inv(ll v) {
	ll x = 1, y = v, p = MOD-2;
	while (p) {
		if (p & 1) x = (x * y) % MOD;
		p >>= 1;
		y = (y * y) % MOD;
	}
	return x;
}

pair<ll,ll> Hval(int l, int r) {
	ll a = ((H[r] - U[r] + MOD) % MOD) * mod_inv((H[l-1] - U[l-1] + MOD) % MOD) % MOD;
	ll b = (H[r] - (a * H[l-1]) % MOD + MOD) % MOD;
	return make_pair(a, b);
}

int main() {
	CPPIO;
	
	cin >> N;
	cin >> (A+1);

	H[0] = 1, U[0] = 2;

	for (int i=1; i<=N; i++) {
		if (A[i] == '0') {
			H[i] = (H[i-1] * H1 + H2) % MOD;
			U[i] = (U[i-1] * H1 + H2) % MOD;
		} else {
			H[i] = (MOD + H3 - H[i-1]) % MOD;
			U[i] = (MOD + H3 - U[i-1]) % MOD;
		}
	}

	int q;
	cin >> q;
	while (q--) {
		int l, r, len;
		cin >> l >> r >> len;
		
		if (Hval(l, l+len-1) == Hval(r, r+len-1)) {
			cout << "Yes" << endl;
		} else {
			cout << "No" << endl;
		}
	}
}

 

 

당분간 Codeforces 대회는 잘 안 나갈 것 같다. 아직 충분히 잘하지 않아서 참가를 해도 레이팅을 많이 올릴 자신이 없다. 체력 문제나 생활패턴 문제만 계속 생기는 것 같다. solved.ac 를 기준 다이아 120개 이상 풀고난 후 강해진 상태에서 대회를 참여해봐야겠다.