Boj 15064) Marblecoin

문제

백준 15064

설명

기본적인 문제의 아이디어는 문자열 장식 과 똑같다. 스택을 문자열로 생각하고, 두 문자열을 비교했을 때 한 문자열이 다른 문자열의 부분문자열이면 길이가 큰 쪽을, 그렇지 않으면 사전 순으로 더 작은 쪽을 먼저 사용하는 것이다.

문제는 문자열 비교 비용이 크기 때문에 이를 최적화해야 한다는 것이다. 여기서 사용할 수 있는 것이 Suffix Array 로 얻을 수 있는 부분문자열의 순서이다. i 번째 스택에서 j 번 물건을 훔쳤다면 i 번째 스택까지의 누적인덱스에서 j 를 더한 인덱스를 통해 Suffix Array 를 조회할 수 있다.

이때 구현을 간단하게 하는 팁은 각 스택을 합칠 때 마지막에 범위를 초과하는 값을 추가로 넣는 것이다. 이러면 사전순으로만 정렬해도 자동으로 한쪽이 다른쪽의 부분문자열인 경우를 처리할 수 있다.

참고로 사전순이므로 역방향부터 그리디하게 접근하면 안된다.

시간 복잡도

O(\(\mathrm{M}\log{\mathrm{M}}\))

• 이때 \(M\) 은 총 마블 수

코드

const int MOD = 1e9 + 7;
const int SPLITV = 302;
const int MAX_IN = 500001;

template<int SIZE = 4* MAX_IN, int CSIZE = 305>
struct SuffixArray
{
	vector<int> src; int len = -1;
	int sa[SIZE];

	// 내부사용값
	int rk[SIZE], cnt[SIZE], tmp[SIZE];
	int o = 1;

	inline bool Cmp(int a, int b)
	{
		if (rk[a] != rk[b]) return rk[a] < rk[b];
		if (a + o < len && b + o < len)
			return rk[a + o] < rk[b + o];
		return  a + o > b + o;
	}

	void CountSort()
	{
		int m = max(rk[sa[len - 1]] + 1, CSIZE) + 1;
		fill(cnt, cnt + m, 0);
		for (int i = 0; i < len; i++) cnt[i + o < len ? rk[i + o] + 1 : 0]++;
		for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
		for (int i = len - 1; i >= 0; i--) tmp[--cnt[i + o < len ? rk[i + o] + 1 : 0]] = i;

		fill(cnt, cnt + m, 0);
		for (int i = 0; i < len; i++) cnt[rk[i]]++;
		for (int i = 1; i < m; i++) cnt[i] += cnt[i - 1];
		for (int i = len - 1; i >= 0; i--) sa[--cnt[rk[tmp[i]]]] = tmp[i];
	}

	void Init()
	{
		len = src.size();
		int p, i;

		//Manber-Myers Algorithms
		for (i = 0; i < len; i++) rk[i] = src[i];
		for (p = 0, o = 1; p + 1 < len; o <<= 1)
		{
			CountSort();
			p = tmp[sa[0]] = 0;
			for (int i = 1; i < len; i++)
				tmp[sa[i]] = Cmp(sa[i - 1], sa[i]) ? ++p : p;
			swap(tmp, rk);
		}
	}
};

SuffixArray sf;
vector<int> acc_pos;
std::vector<pair<int, int>> iters[MAX_IN]; // first 문자열의 second 번째 문자
struct compare {
	bool operator() (pair<int, int>& a, pair<int, int>& b) {
		return sf.rk[acc_pos[a.first] + a.second] > sf.rk[acc_pos[b.first] + b.second];
	}
};

int main(void)
{
	int n; cin >> n;
	for (int i = 0; i < n; i++)
	{
		int k; cin >> k;
		acc_pos.push_back(sf.src.size());
		while (k--) cin >> sf.src.emplace_back();
		sf.src.push_back(SPLITV); // 구분 문자용
	}
	acc_pos.push_back(sf.src.size());
	sf.src.push_back(301); // \0 문자용
	sf.Init();

	priority_queue<pair<int, int>, vector<pair<int, int>>, compare> pq;
	for (int i = 0; i < n; i++) pq.push({ i, 0 });

	long long ans = 0;
	while (!pq.empty())
	{
		auto a = pq.top(); pq.pop();
		int value = sf.src[acc_pos[a.first] + a.second];
        ans = (ans + value) * 365 % MOD;
		//cout << value << endl;
		if (acc_pos[a.first] + a.second + 2 < acc_pos[a.first + 1]) pq.push({a.first, a.second+1});
	}
	cout << ans;
}