Codeforces Round #438 (Div.1 + Div.2) D. Huge Strings

D. Huge Strings

http://codeforces.com/contest/868/problem/D

이 문제는 cubelover님 덕분에 완전히 이해할 수 있었다.

mx가 얼마 되지 않는다는 것을 이해하고 나면, 구현은 어렵지 않다.

문제 정황상 대충 작을거로는 처음부터 짐작이 되는데... 이유는 정확히 모르겠고,

내가 생각했던 값은 충분히 시간안에 구할 수 없을만큼 큰데 어떻게 해야할지 모르겠어서

걍 대충 만들어서 제출해봤는데 콘테중에는 AC받았음... but 역시나 시스페일 먹었다.

일단 핵심은 스트링을 2개 붙여봐야 길이가 k인 부분스트링(substring)이 새롭게 만들어지는 개수는 k-1개가 최대라는 거다.

이해가 안가면 그림을 그려서 길이가 k보다 큰 스트링 2개를 붙인다음에 새롭게 만들어지는 길이가 k인 스트링 갯수를 세보면 된다.

우와ㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏ

일단 그럼 처음 어떻게 생각해야하는지부터 보자.

길이가 100짜리인 스트링을 계속 최악으로 불려나가면,

100->200->400->800->... 이렇게 된다.

그럼 최악의 스트링 길이는 100*2^100인데 이는 2^107보다는 작으니까 k가 답이 될 수 있는 최대값은 106이다.

그럼 스트링의 길이가 어떻든 간에 두 스트링을 합쳐서 길이가 106이면서 기존에 없던 새로운 스트링이 최대 몇개나 나올 수 있을까?

그건 105개이다~!

그러므로 이러한 행동을 100번 해봐야 만들 수 있는 새로운 스트링의 개수는 105*100개밖에 되지 않는다.

하지만 k=106이 답이 되려면 새롭게 만들어지는 스트링의 개수는 2^106개가 되어야 할 것이다.

그러므로 당연히 k값으로 106은 불가능하다.

이런식으로 생각해보면 k=10일때에도 새롭게 만들어지는 스트링의 개수는 최대 9*100개이며,

기존에 가지고 있던 스트링 100개가 모두 다 다른 길이 10짜리 부분스트링을 가지고 있다고 해도 그러한 부분스트링의 개수는 100*100개를 벗어날 수 없다. (왜냐하면 스트링 최대 길이가 100이니까 10짜리 부분스트링은 최대 100개(사실은 91개) 가지고 있을 수 있고, 이러한 스트링이 최대 100개까지 있으니까)

따라서 set에 길이가 10인 부분스트링을 저장해봐야 최대 개수는 약 11000개 보다도 안된다는 것이다.

길이가 k인 이진수를 2^k개 만큼 무식하게 늘여놓는다면 k*2^k인데, 사실 부분스트링이 중첩되 될 것이므로 이거보다는 작을 것이다.

그래서 k*2^k이 1만쯤 되는 k값을 알아보니 약 10정도 되니까... 대충 3개정도 더 더해서 mx값이 13은 되지 않을까 추측해 볼 수 있다.

물론 실제 답은 이거보다 작을 것이다.

생각해보니 문제 설명을 안했는데,

어차피 내가 리마인드 할 용도로 썼으니까... 문제 읽는건 알아서 하시길ㅋㅋㅋ

문제 입력은 아래와 같다.

input

5
01
10
101
11111
0
3
1 2
6 5
4 4

output

1
2
0

AC받은 코드는 아래와 같다.

#include <iostream>
#include <set>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;
set<string> st[201][14];
string pre[201], sfx[201], s[101];
const int mx = 13;
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    for(int i=0; i<n; i++) {
        cin >> s[i];
        for(int j=0; j<s[i].size(); j++) {
            for(int k=j; k<s[i].size(); k++) {
                int len = k-j+1;
                if(len > mx) break;
                st[i][len].emplace(s[i].begin()+j, s[i].begin()+k+1);
            }
        }
 
        if(s[i].size()<mx) pre[i] = sfx[i] = s[i];
        else {
            pre[i]=string(s[i].begin(), s[i].begin()+mx);
            sfx[i]=string(s[i].end()-mx, s[i].end());
        }
    }
 
    int m; cin >> m;
    for(int i=n; i<n+m; i++) {
        int a,b; cin >> a >> b;
        a--; b--;
        for(int j=1; j<=mx; j++) {
            for(auto it : st[a][j]) st[i][j].emplace(it);
            for(auto it : st[b][j]) st[i][j].emplace(it);
        }
 
        string str = sfx[a]+pre[b];
        for(int j=0; j<str.size(); j++) {
            for(int k=j; k<str.size(); k++) {
                int len = k-j+1;
                if(len > mx) break;
                st[i][len].emplace(str.begin()+j, str.begin()+k+1);
            }
        }
 
        int ans=1;
        for(; ans<=mx; ans++) if(st[i][ans].size() != (1<<ans)) break;
        printf("%d\n", ans-1);
 
        if(pre[a].size() >= mx) pre[i]=pre[a];
        else {
            pre[i]=pre[a]+pre[b];
            pre[i]=pre[i].substr(0,min(mx,int(pre[i].size())));
        }
 
        if(sfx[b].size() >= mx) sfx[i]=sfx[b];
        else {
            sfx[i]=sfx[a]+sfx[b];
            int tmp = min(mx, int(sfx[i].size()));
            sfx[i]=sfx[i].substr(sfx[a].size()+sfx[b].size()-tmp, tmp);
        }
    }
    return 0;
}