BOJ 10351 Circle of digits

문제 링크입니다.

문제 요약

길이가 N인 원형 수열이 주어집니다. 이를 K개의 마디로 잘라내었을 때, 각 마디가 나타내는 수의 최댓값을 최소화하세요.

풀이

길이가 길수록 큰 수입니다. 최대한 균등하게 마디를 자르는 것이 좋음을 알 수 있고, 이로부터 최댓값의 길이를 구할 수 있습니다. 이를 적당히 L로 둡시다.

주어진 수열이 선형이였다고 생각해 봅시다. 최댓값을 결정했다면 맨 앞 자리부터 순서대로 L자리를 확인해 결정한 최댓값보다 크면 L-1자리, 작거나 같으면 L자리 마디를 만드는 그리디한 전략을 사용할 수 있습니다. 이는 하나의 최댓값에 대해 $\mathcal{O}(N)$에 가능하므로, 모든 L자리 수에 대해 이분 탐색하면 시간복잡도가 $\mathcal{O}(NL)$이 됩니다.

모든 L자리 수를 사용하는 대신 순열에서 찾을 수 있는 N개의 수만을 가지고 이분 탐색을 해도 충분합니다. 이를 위해 각 자리에서 시작하는 L자리 수의 크기를 비교해야 합니다. 이는 주어진 문자열을 2배로 늘린 뒤 Suffix Array를 구하는 방식으로 해결할 수 있습니다. Suffix Array를 구하는 데 $\mathcal{O}(N \lg N)$의 시간이 필요합니다. 이를 구하고 나면 이분 탐색 역시 $\mathcal{O}(N \lg N)$의 시간이 필요합니다.

수열이 원형인 경우에는 마디의 시작점을 알 수 없습니다. 마디의 길이가 L 이하인 점에서 착안해, 수열의 첫 L개 자리 중 마디를 시작할 수 있는 위치가 적어도 하나 존재함을 알 수 있습니다. 총 L개의 자리에서 시작했을 때 수열을 한 바퀴 돌 때까지 한 번에 L자리 또는 L-1자리만큼 건너뛰므로, $\mathcal{O}(N / L)$의 시간이 필요합니다. 따라서 한 번의 이분 탐색 스텝이 여전히 $\mathcal{O}(N)$이므로, 총 시간 복잡도 $\mathcal{O}(N \lg N)$에 문제를 해결할 수 있습니다.

Suffix Array를 $\mathcal{O}(N \lg^2 N)$에 구해도 문제를 해결하기에 충분합니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

vector<int> ret, rev;

void SA(string s){
	int n = s.size(); int m = max(n, 1024)+1;
	vector<int> sa(n), r(2*n), nr(2*n), cnt(m), idx(n);
	for(int i = 0; i < n; i++) sa[i] = i, r[i] = s[i]-'0'+1;
	for(int d = 1; d < n; d <<= 1){
		auto cmp = [&](int i, int j){
			return r[i] < r[j] || r[i] == r[j] && r[i+d] < r[j+d];
		};
		for(auto& i : cnt) i = 0;
		for(int i = 0; i < n; i++) cnt[r[i+d]]++;
		for(int i = 1; i < m; i++) cnt[i] += cnt[i-1];
		for(int i = n-1; i>=0; i--) idx[--cnt[r[i+d]]] = i;
		for(auto& i : cnt) i = 0;
		for(int i = 0; i < n; i++) cnt[r[i]]++;
		for(int i = 1; i < m; i++) cnt[i] += cnt[i-1];
		for(int i = n-1; i>=0; i--) sa[--cnt[r[idx[i]]]] = idx[i];
		nr[sa[0]] = 1;
		for(int i = 1; i < n; i++) nr[sa[i]] = nr[sa[i-1]] + cmp(sa[i-1], sa[i]);
		for(int i = 0; i < n; i++) r[i] = nr[i];
	}
	ret.resize(n/2); rev.resize(n/2); int ii = 0;
	for(int i : sa) if(i < n/2){
		rev[i] = ii;
		ret[ii++] = i;
	}
	return;
}

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	int n, k; cin >> n >> k;
	string s; cin >> s; s = s+s;
	if(n == k){
		int ans = 0;
		for(int i = 0; i < n; i++) ans = max(ans, s[i]-'0');
		return !(cout << ans);
	}
	SA(s);
	int l = 0, r = n;
	while(l < r){
		int mid = l+r>>1;
		bool flag = 0;
		for(int x = 0; x < (n-1)/k+1; x++){
			int cnt = 0; int now = x;
			while(now < x+n){
				if(rev[now%n] <= rev[ret[mid]]) now++;
				now += (n-1)/k;
				cnt++;				
			}
			if(cnt <= k){
				flag = 1;
				break;
			}
		}
		if(flag) r = mid;
		else l = mid+1;
	}
	cout << s.substr(ret[l], (n-1)/k+1);
}