結果

問題 No.205 マージして辞書順最小
ユーザー anta
提出日時 2015-05-08 22:26:13
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 8,219 bytes
コンパイル時間 1,144 ms
コンパイル使用メモリ 99,388 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-05 20:21:50
合計ジャッジ時間 1,839 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii; typedef long long ll;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
class SuffixArray {
public:
    typedef char Alpha;
    typedef int Index;
    void build(const Alpha *str, Index n, int AlphaSize);
    void build(const Alpha *str, Index n);
    inline Index getKThSuffix(Index k) const { return suffixArray[k]; }
    inline Index length() const { return suffixArray.size() - 1; }
    std::vector<Index> suffixArray;
    template<typename AlphaT> void sa_is(const AlphaT *str, Index n, int AlphaSize, Index *sa, std::vector<Index> &bucketOffsets);
    template<typename AlphaT> void inducedSort(const AlphaT *str, Index n, int AlphaSize, const std::vector<bool> &types, Index *sa, std::vector
        <Index> &bucketOffsets);
    template<typename AlphaT> void countingAlphabets(const AlphaT *str, Index n, int AlphaSize, std::vector<Index> &bucketOffsets, bool b = false);
    template<typename AlphaT> void getBucketOffsets(const AlphaT *str, Index n, bool dir, int AlphaSize, std::vector<Index> &bucketOffsets);
    void buildInverseSuffixArray();
    std::vector<Index> inverseSuffixArray;
};
void SuffixArray::build(const Alpha *str, Index n, int AlphaSize) {
    suffixArray.resize(n+1);
    if(n == 0) suffixArray[0] = 0;
    else {
        //I = sizeof(Index) * CHAR_BITS として
        //suffixArray + bucketOffsets + types + 関数ローカル変数
        //= n*I + max(AlphaSize, n/2)*I + 2*n + O(log n) bits
        //I = 4 * 32でAlphaSizeが十分小さいとすると:
        //(6+1/16) * n + O(log n) bytes
        std::vector<Index> bucketOffsets(std::max(AlphaSize, (n+1) / 2) + 1);
        sa_is<Alpha>(str, n, AlphaSize, &suffixArray[0], bucketOffsets);
    }
}
void SuffixArray::build(const Alpha *str, Index n) {
    Alpha maxElem = *std::max_element(str, str + n);
    assert(maxElem+0 < std::numeric_limits<int>::max());
    build(str, n, (int)(maxElem+1));
}
//strは[0,n)が有効で番兵は含まれない。saは[0,n]が有効
template<typename AlphaT>
void SuffixArray::sa_is(const AlphaT *str, Index n, int AlphaSize, Index *sa, std::vector<Index> &bucketOffsets) {
    std::vector<bool> types(n+1);
    types[n-1] = 0; types[n] = 1;
    for(Index i = n-2; i >= 0; i --)
        types[i] = str[i] < str[i+1] || (str[i] == str[i+1] && types[i+1]);
    countingAlphabets(str, n, AlphaSize, bucketOffsets);
    getBucketOffsets(str, n, true, AlphaSize, bucketOffsets);
    std::fill(sa, sa + n + 1, -1);
    for(Index i = 1; i < n; i ++)
        if(types[i] && !types[i-1]) sa[-- bucketOffsets[(int)str[i]]] = i;
    sa[0] = n;
    inducedSort(str, n, AlphaSize, types, sa, bucketOffsets);
    Index n1 = 0;
    for(Index i = 0; i <= n; i ++) {
        Index j = sa[i];
        if(j > 0 && types[j] && !types[j-1]) sa[n1 ++] = j;
    }
    //LMS substringsを番号付けする。sa[0..n1-1]にソートされている。
    //メモリのためにsaの右半分をバッファに利用する。
    //さらにそこでposの順序で整数ソートすることを同時に行う。
    //ここでLMS substringが連続して現れないことやLMS substringの数がn/2以下であることを利用してなんとか1つの配列でやる
    Index *buffer = sa + n1;
    std::fill(buffer, sa + n + 1, -1);
    Index uniqueLMSCount = 0, prevPos = -1;
    assert(sa[0] == n);
    buffer[sa[0] / 2] = uniqueLMSCount ++;  //'$'
    for(Index i = 1; i < n1; i ++) {
        Index pos = sa[i]; bool diff = false;
        if(prevPos == -1) diff = true;
        else for(Index j = pos, k = prevPos; ; j ++, k ++) {
                if(str[j] != str[k] || types[j] != types[k]) {
                    diff = true;
                    break;
                }else if(j != pos && ((types[j] && !types[j-1]) || (types[k] && !types[k-1])))
                    break;
            }
        if(diff) {
            uniqueLMSCount ++;
            prevPos = pos;
        }
        buffer[pos / 2] = uniqueLMSCount - 1;
    }
    for(Index i = n, j = n; i >= n1; i --)
        if(sa[i] >= 0) sa[j --] = sa[i];
    Index *sa1 = sa, *s1 = sa + n + 1 - n1;
    if(uniqueLMSCount == n1)
        for(Index i = 0; i < n1; i ++) sa1[s1[i]] = i;
    else
        sa_is<Index>(s1, n1 - 1, uniqueLMSCount, sa1, bucketOffsets);
    countingAlphabets(str, n, AlphaSize, bucketOffsets);
    getBucketOffsets(str, n, true, AlphaSize, bucketOffsets);
    for(Index i = 1, j = 0; i <= n; i ++)
        if(types[i] && !types[i-1]) s1[j ++] = i;
    for(Index i = 0; i < n1; i ++) sa1[i] = s1[sa1[i]];
    std::fill(sa + n1, sa + n + 1, -1);
    for(Index i = n1-1; i >= 1; i --) {
        Index j = sa[i]; sa[i] = -1;
        sa[-- bucketOffsets[(int)str[j]]] = j;
    }
    inducedSort(str, n, AlphaSize, types, sa, bucketOffsets);
}
template<typename AlphaT>
void SuffixArray::inducedSort(const AlphaT *str, Index n, int AlphaSize, const std::vector<bool> &types, Index *sa, std::vector<Index> &bucketOffsets
    ) {
    getBucketOffsets(str, n, false, AlphaSize, bucketOffsets);
    for(Index i = 0; i < n; i ++) {
        Index j = sa[i] - 1;
        if(j >= 0 && !types[j]) sa[bucketOffsets[(int)str[j]] ++] = j;
    }
    getBucketOffsets(str, n, true, AlphaSize, bucketOffsets);
    for(Index i = n; i >= 1; i --) {
        Index j = sa[i] - 1;
        if(j >= 0 && types[j]) sa[-- bucketOffsets[(int)str[j]]] = j;
    }
}
template<typename AlphaT>
void SuffixArray::countingAlphabets(const AlphaT *str, Index n, int AlphaSize, std::vector<Index> &bucketOffsets, bool b) {
    if(b || (int)bucketOffsets.size() / 2 >= AlphaSize) {
        std::vector<Index>::iterator alphabetCounts =
            b ? bucketOffsets.begin() : bucketOffsets.begin() + AlphaSize;
        std::fill(alphabetCounts, alphabetCounts + AlphaSize, 0);
        for(Index i = 0; i < n; i ++)
            alphabetCounts[(int)str[i]] ++;
    }
}
template<typename AlphaT>
void SuffixArray::getBucketOffsets(const AlphaT *str, Index n, bool dir, int AlphaSize, std::vector<Index> &bucketOffsets) {
    //AlphaSizeが大きい場合にはbucketOffset求めるたびにalphabetを数えてメモリ量を少なくし、
    //AlphaSizeが小さい場合にはbucketOffsetをalphabetCountsと別の場所に置くことにする。
    std::vector<Index>::iterator alphabetCounts;
    if((int)bucketOffsets.size() / 2 < AlphaSize) {
        countingAlphabets(str, n, AlphaSize, bucketOffsets, true);
        alphabetCounts = bucketOffsets.begin();
    }else alphabetCounts = bucketOffsets.begin() + AlphaSize;
    Index cumsum = 1;   //'$'の分
    if(dir) {
        for(int i = 0; i < AlphaSize; i ++) {
            cumsum += alphabetCounts[i];
            bucketOffsets[i] = cumsum;
        }
    }else {
        for(int i = 0; i < AlphaSize; i ++) {
            Index x = alphabetCounts[i];
            bucketOffsets[i] = cumsum;
            cumsum += x;
        }
    }
}
void SuffixArray::buildInverseSuffixArray() {
    Index n = length();
    inverseSuffixArray.resize(n+1);
    for(Index i = 0; i <= n; i ++)
        inverseSuffixArray[suffixArray[i]] = i;
}
struct StringInterspersal {
    string minimum(vector <string> W) {
        int n = W.size();
        string w; vi d;
        rep(i, n) {
            d.pb(w.size());
            w += W[i];
            w += '~';
        }
        SuffixArray sa;
        sa.build(&w[0], w.size());
        sa.buildInverseSuffixArray();
        vi v(n);
        string s;
        while(1) {
            pair<int,int> p(INF,-1);
            rep(i, n) if(v[i] != W[i].size()) {
                p = min(p, mp(sa.inverseSuffixArray[d[i] + v[i]], i));
            }
            if(p.second == -1) break;
            s += W[p.second][v[p.second]];
            v[p.second] ++;
        }
        return s;
    }
};
int main() {
    int N;
    cin >> N;
    vector<string> W(N);
    rep(i, N) cin >> W[i];
    string ans = StringInterspersal().minimum(W);
    cout << ans << endl;
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
1