알고스팟 팬미팅 FANMEETING

 

https://algospot.com/judge/problem/read/FANMEETING

algospot.com :: FANMEETING

 

 

<접근방법>

입력값이 커서 완전탐색으로는 안된다는 것을 알 수 있다.(댓글보면 정답처리가 되는 거 같긴 합니다.)

문제를 보면 무언가 규칙이 있어 보입니다.(결국 발견실패..ㅠㅠ)

책을 참고해서 보면 이러한 규칙이 있다는 것을 알 수 있습니다.

 

그림1

 

밑줄 친 부분을 나열해서 보면..

 

 

A의 순서만 뒤집어 준다면 문제에서 정의한 팬미팅의 모습이 나옵니다.

남자를 1, 여자를 0이라고 하면 An*Bn의 값이 0이 되면 포옹하는 것이 되겠죠.

그림1의 밑줄 친 부분의 연산이 끝났을 때, 값이 0이 된다면 모두가 포옹하는 것이 됩니다.

 

그렇다면 곱셈 연산의 시간을 줄이는 것이 관건이겠네요.

일반적인 두 큰 수를 곱셈하는 알고리즘을 사용한다면 O(n^2)으로 완전탐색과 차이점이 없습니다.

그래서 카라츠바 알고리즘을 사용하여 곱셈을 구현합니다.

 

 

 

---

 

 

<코드>

카라츠바 알고리즘의 normalize는 자릿수 처리인데 이 문제에서는 두 수 모두 0, 1로만 이루어져 있기 때문에

필요가 없습니다.

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

int tc;

void normalize(vector<int>& c) {
	//가장 큰 자릿수 올림땜에
	c.push_back(0);
	for (int i = 0; i < c.size()-1; i++) {
		if (c[i] < 0) {
			int borrow = (abs(c[i]) + 9) / 10;
			c[i + 1] -= borrow;
			c[i] += borrow * 10;
		}
		else {
			c[i + 1] += c[i] / 10;
			c[i] %= 10;
		}
	}
	while (c.size() > 1 && c.back() == 0) c.pop_back();
}

vector<int> multiply(const vector<int> &a, const vector<int> &b) {
	vector<int> c(a.size() + b.size() + 1, 0);

	for (int i = 0; i < a.size(); i++) {
		for (int j = 0; j < b.size(); j++) {
			c[i + j] += (a[i] * b[j]);
		}
	}

	//normalize(c);
	return c;
}

//a += b*(10^k)
void addTo(vector<int>& a, const vector<int>& b, int k) {
	a.resize(max(a.size(), b.size() + k));

	for (int i = 0; i < b.size(); i++) {
		a[i + k] += b[i];
	}

	////정규화 normalize
	//for (int i = 0; i < a.size(); i++) {
	//	if (a[i] > 10) {
	//		a[i + 1] += a[i] % 10;
	//		a[i] /= 10;
	//	}
	//}
}

//a -= b a>=b를 가정
void subFrom(vector<int>& a, const vector<int>& b) {
	a.resize(max(a.size(), b.size())+1); //+1 없어도 된다

	for (int i = 0; i < b.size(); i++) {
		a[i] -= b[i];
	}

	////정규화
	//for (int i = 0; i < a.size(); i++) {
	//	if (a[i] < 0) {
	//		a[i] += 10;
	//		a[i + 1] -= 1;
	//	}
	//}
}

vector<int> karatsuba(const vector<int>& a, const vector<int>& b) {
	//a가 사이즈가 더 작으면 바꿔서 계산
	int an = a.size(), bn = b.size();

	if (an < bn) return karatsuba(b, a);

	//기저사례
	//-a나 b가 비어있는 경우
	if (an == 0 || bn == 0) return vector<int>();//빈 벡터

	//system("pause");
	//-사이즈가 50보다 작으면 그냥 곱셈으로
	if (an <= 50) return multiply(a, b);

	int half = an / 2;

	//a와 b를 반띵
	vector<int> a0(a.begin(), a.begin() + half);
	vector<int> a1(a.begin() + half, a.end());
	vector<int> b0(b.begin(), b.begin() + min<int>(bn, half));//<int>가 왜 붙냐
	vector<int> b1(b.begin() + min<int>(bn, half), b.end());

	//z 구하기
	vector<int> z2 = karatsuba(a1, b1);
	vector<int> z0 = karatsuba(a0, b0);
	
	addTo(a0, a1, 0);
	addTo(b0, b1, 0);

	//z1 = (a0 * b0) - z0 - z2
	vector<int> z1 = karatsuba(a0, b0);
	subFrom(z1, z0);
	subFrom(z1, z2);

	//z 합치기
	vector<int> res;
	addTo(res, z0, 0);
	addTo(res, z1, half);
	addTo(res, z2, half * 2);

	return res;
}


void simul(const string& s1, const string& s2) {
	int n = s1.size(), m = s2.size();
	vector<int> A(n), B(m);

	for (int i = 0; i < n; i++) {
		A[i] = (s1[i] == 'M') ? 1 : 0;
	}
	for (int i = 0; i < m; i++) {
		B[m-i-1] = (s2[i] == 'M') ? 1 : 0;
	}

	vector<int>C = karatsuba(A, B);
	int cnt = 0;
	for (int i = n - 1; i < m; i++) {
		if (C[i] == 0) cnt++;
	}
	cout << cnt << '\n';
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> tc;
	while (tc--) {
		string s[2];

		for (int i = 0; i < 2; i++) {
			cin >> s[i];
		}
		
		simul(s[0], s[1]);
	}
	return 0;
}

 

 

 

 

 

 

[참고]

-프로그래밍대회에서 배우는 알고리즘 문제 해결 전략1