BOJ 15338 String Puzzle

문제 링크입니다.

문제 요약

엄청 긴 문자열이 있습니다. 우리는 이 문자열의 몇몇 글자가 무엇인지와, 몇몇 부분문자열의 쌍이 서로 같다는 힌트를 알고 있습니다. 이 힌트를 통해 문자열의 몇 번째 글자가 무엇인지 묻는 쿼리에 답해야 합니다.

입력이 이상해요

입력 형식을 이해하는 데 좀 걸렸고, 그 의미를 이해하고 얼마 지나지 않아 풀이 아이디어가 나왔습니다. 힌트 A와 쿼리의 입력은 단순하니까 넘어가고, 힌트 B의 입력에 주목합시다.

힌트 B의 입력은 두 배열 $h$와 $y$로 관리할 수 있습니다. 이때 $h[i] < y[i]$와 $y[i] < y[i+1]$이 성립하도록 입력이 주어집니다.

우리에게 주어진 것은 $h[i]$가 0이 아니라면 $y[i]$부터 $y[i+1]-1$까지의 구간이 $h[i]$부터 같은 길이만큼의 구간과 서로 같다는 것입니다. 이때 $y$에 의해 결정되는 구간이 서로 겹치지 않기 때문에, $y$에서의 구간의 각 원소는 정확히 하나의 $h$에서의 구간의 원소에 대응됩니다.

집합 만들기, like 분리 집합

따라서 우리는 각 원소를 $y$-구간에서 $h$-구간으로 미는 것을 반복해 최대한 문자열의 왼쪽에 있는 같은 문자가 쓰인 칸을 찾아낼 수 있습니다. $y$-구간과 $h$-구간이 서로 겹치는 경우 겹치는 구간을 벗어날 때까지 칸을 당겨올 수 있기 때문에, 간단한 모듈러 연산으로 각 구간마다 $O(1)$에 $y$ 구간에서 $h$ 구간으로 넘겨줄 수 있습니다. 이렇게 칸을 왼쪽으로 연결, 연결, 연결하면… 구간은 총 $b$세트가 있으므로 $O(b)$만에 임의의 칸을 같은 문자를 갖는 가장 왼쪽의 칸으로 옮길 수 있습니다.

이제 우리는 맨 왼쪽 칸을 분리 집합에서의 루트처럼 다룰 수 있습니다. 힌트 A에서 주어진 문자를 그 위치의 루트에 저장하고, 쿼리가 주어질 때마다 그 위치의 루트에 적힌 문자를 확인해 출력하는 것으로 충분합니다. 총 $a+q$번 인덱스를 왼쪽으로 밀어야 하고, 매번 $O(b)$의 시간이 필요하니, 총 시간 복잡도 $O((a+q)b)$에 문제를 해결할 수 있습니다.

인덱스가 커서 map 을 사용했습니다. unordered_map 을 사용해도 아마 괜찮을 텐데… 시간이 그리 빡빡하지 않으니 그냥 map 으로 해주는 게 안전하다고 생각합니다.

코드

#include<bits/stdc++.h>
using namespace std;
using pic = pair<int, char>;

int n, a, b, q, y[1010], h[1010];
map<int, char> ans;
vector<pic> qa;

int f(int x){
	for(int i = b; i >= 1; i--){
		if(y[i+1] <= x) break;
		if(x < y[i]) continue;
		if(!h[i]) break;
		x = (x-y[i])%(y[i]-h[i])+h[i];
	}
	return x;
}

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	cin >> n >> a >> b >> q;
	qa.resize(a); for(auto& [x, c] : qa) cin >> x >> c;
	for(int i = 1; i <= b; i++) cin >> y[i] >> h[i];
	y[b+1] = n+1;
	for(auto [x, c] : qa) ans[f(x)] = c;
	while(q--){
		int x; cin >> x;
		cout << max('?', ans[f(x)]);
	}
}