Topcoder SRM 528 Div1(Medium) SPartition

https://community.topcoder.com/stat?c=problem_statement&pm=11634

\(1\leq{N}\leq{40}\)

o와 x로 이루어진

길이가 N인 문자열 S가 입력으로 들어올 때, 이 문자열에 포함된 각각의 문자들에 대해서 s1문자열 맨뒤에 붙일것인지

s2문자열 맨뒤에 붙일것인지를 결정한다. 그리고 최종적으로 s1과 s2가 같게 만드는 방법의 수를 모두 구하는 문제이다.

참고로 각 문자들은 구분할 수가 있기 때문에 최종 문자열이 같더라도 S상에서의 위치로 변환해봤을 때

다르다면 방법이 다른것이므로 둘 다 셀 것이다.

우선 naive 하게 생각하여 모든 경우의 수를 세면서 두 문자열을 비교하여 같다면 더해주는 방식이 있을 것이다.

이 방법은 우선 각각의 문자가 어떤 문자열에 들어갈지 선택해야하고 다 선택한뒤 두 문자열을 비교하기 때문에

\(O(N\cdot{2^N})\) 이 걸린다. N이 최대 40이기 때문에 시간안에 못돈다. 그럼 어떻게 할까?

이 때 좋은 방법이 길이 40의 문자열을 둘로 쪼개서 각각의 모든경우를 구해놓은뒤에 한쪽 반띵에 대해

구해놓은 모든 경우에 대해 합쳤을 때 두 문자열이 같게 되는 반대쪽반띵만을 보는 방식으로 할 수가 있다.

그러면 우선 반띵에 대해 모든 경우를 따지는것은 \(O(2^{N/2}\) 이기 때문에 충분히 시간안에 돌아간다.

그럼 왼쪽 반띵을 L, 오른쪽 반띵을 R 이라고 해보자.

L에서 각각의 문자를 s1에 붙여줄건지 s2에 붙여줄건지를 비트마스크로 모든경우를 봐준다.

각 경우에 실제로 s1와 s2에 문자들을 넣어주고나서 s1와 s2의 앞부분이 일치하는지를 보고

아니면 그냥 버린다. 왜냐하면 R과 붙였을 때 최종적으로 같아져야하는데 애초에 왼쪽에서부터 다르면

최종적으로도 당연히 다르기 때문이다. 그리고 앞부분이 일치한다면 긴쪽의 겹치지 않는 부분만 빼서

map 으로 센다. (나는 s1와 s2 어느쪽이 남는지를 표시하기 위해 map<pair<string,string>> 으로 했다.)

그러면 R에서 어떤것과 지금 이것이 붙어서 전체 문자열이 같아질 수 있을까?

조금만 생각해보면 L에서 남은 문자열이 R에서도 남아야되며 서로 다른쪽이 남아야 된다는 것을 알 수가 있다.

예를들어

L에서 s1 = oxoo 이고 s2 = ox 라면

R에서 s1 = xo    이고 s2 = ooxo 여야

합쳐서 같아지는 것이다. 그리고 L에서는 oo 가 남고 R에서도 oo 가 남는 다는 것을 알 수가 있다.

그리고 R에서는 물론 반대로 뒤쪽이 같은지를 보고 뒤쪽 겹치는 부분 외의 남는 부분으로 계산하여야 한다.

L와 R 각각에서 생성된 s1와 s2를 합치는 모습을 상상해보면 쉽게 알 수가 있다.

즉 L에서 남는 상태를 ("oo", "") 로 나타낸다면 R에서 남는 상태를 ("", "oo") 로 나타낼 수 있으므로 결국

남는 상태가 뒤바뀐 두개가 만나면 결과적으로 문자열s1과 s2가 같아지기 때문에 이걸 세면된다.

그러면 R에서도 똑같이 모든 경우의 수를 비트마스크로 봐주면서 남는부분을 map으로 세주면서

반대쪽에 합쳐서 최종적으로 같아지는 놈의 수만큼 답에 누적해주면 답을 구할 수가 있다.

R도 미리 다 구해놓고 다시 L에서 돌면서 곱하는식으로해도된다.

시간복잡도를 계산해보자면 우선 반띵에서 모든경우를 돌며 문자열 비교를 했기 때문에 \(O(N\cdot{2^N})\)

그리고 최악의 경우 O(2^N) 개를 map에 삽입하며 문자열 비교에 O(N) 이기 때문에 \(O(N^2\cdot{2^N})\) 

최종 복잡도 \(O(N^2\cdot{2^N})\) 가 나오는데 조금 간당간당하다 실제로 돌려보니 최대 1.9초 까지 걸린다.

정말 간당간당하게 AC를 받긴했지만 위험부담이있기 때문에 pair<string,string> 대신 string을 long long 으로 바꿔주자

x는0으로 o는1로 하여 비트마스크로 하려고 봤더니 문자열의 길이가 일정한게 아니기 때문에 x와 xxxxx를

구분하지 못한다는 문제가 있다. 그래서 삼진법과 같은식으로 하면 \(O(N\cdot{2^N})\) 으로 줄일 수 있을 것이다.

일단 귀찮으므로 string 으로 한 코드를 올린다.

#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;++i)
#define FOR(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
#define inp1(a) scanf("%d",&a)
#define inp2(a,b) scanf("%d%d",&a,&b)
#define inp3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define inp4(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d)
#define inp5(a,b,c,d,e) scanf("%d%d%d%d%d",&a,&b,&c,&d,&e)
#define fastio() ios_base::sync_with_stdio(false),cin.tie(NULL)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<int> vi; 
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<vector<int> > vvi;
typedef pair<int,pair<int,int> > piii;
typedef vector<piii> viii;
const double EPSILON = 1e-9;
const double PI = acos(-1);
const int MOD = 1e9+7;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
const int MAX_N = 102;
 
class SPartition {
public:
    map<pair<string, string>, long long > mp1, mp2;
    long long getCount(string s) {
        long long ans = 0;
        int N = s.size();
        string L = s.substr(0, N/2);
        string R = s.substr(N/2, N/2);
        
        for(int i = 0 ; i < (1<<(N/2)); i++){
            string l, r;
            for(int j = 0 ; j < N/2; j++){
                if(i & (1<<j)) l += L[j];
                else r += L[j];
            }
            if(l.size() == r.size()) {
                if(l != r) continue;
                mp1[make_pair("","")]++;
            }
            else if(l.size() < r.size()){
                if(l != r.substr(0, l.size())) continue;
                mp1[make_pair("", r.substr(l.size(), r.size() - l.size()))]++;
            }
            else{
                if(l.substr(0, r.size()) != r) continue;
                mp1[make_pair(l.substr(r.size(), l.size() - r.size()), "")]++;
            }
        }
 
        for(int i = 0 ; i < (1<<N/2); i++){
            string l, r;
            for(int j = 0 ; j < N/2; j++){
                if(i & (1<<j)) l += R[j];
                else r += R[j];
            }
            if(l.size() == r.size()) {
                if(l != r) continue;
                mp2[make_pair("","")]++;
            }
            else if(l.size() < r.size()){
                if(l != r.substr(r.size()-l.size(), l.size())) continue;
                mp2[make_pair("", r.substr(0, r.size() - l.size()))]++;
            }
            else{
                if(l.substr(l.size()-r.size(), r.size()) != r) continue;
                mp2[make_pair(l.substr(0, l.size() - r.size()), "")]++;
            }       
        }
 
        for(auto it = mp1.begin(); it != mp1.end(); it++){
            auto p = (*it).first;
            long long cnt1 = (*it).second;
            if(cnt1 == 0) continue;
            p = {p.second, p.first};
            long long cnt2 = mp2[p];
            ans += cnt1 * cnt2;
        }
        return ans;
    }
};