結果

問題 No.3000 Optimal Run Length Encoding
ユーザー kotatsugame
提出日時 2024-12-25 05:06:11
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2,734 ms / 10,000 ms
コード長 3,757 bytes
コンパイル時間 6,207 ms
コンパイル使用メモリ 161,388 KB
実行使用メモリ 327,028 KB
最終ジャッジ日時 2024-12-25 19:54:40
合計ジャッジ時間 143,873 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 142
権限があれば一括ダウンロードができます

ソースコード

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

#include<iostream>
#include<algorithm>
#include<set>
#include<vector>
#include<cassert>
#include<atcoder/string>
using namespace std;
// (p, l, r) : S[l, r) は周期 p かつ極大
// sum_{(p,l,r)} 1 <= n
// sum_{(p,l,r)} (r-l)/p <= 3n
// sum_{(p,l,r)} (r-l+1-2*p) = O(n log n)
template <typename C>
vector<tuple<int, int, int>> run_enumerate(const C& S) {
    int N = S.size();
    using T = tuple<int, int, int>;
    vector<vector<pair<int, int>>> by_p(N + 1);
    auto solve_sub = [&](const C& l, const C& r) {
        vector<T> res;
        int n = l.size(), m = r.size();
        C s = l, t = r;
        t.insert(end(t), begin(l), end(l));
        t.insert(end(t), begin(r), end(r));
        reverse(begin(s), end(s));
        auto ZS = atcoder::z_algorithm(s), ZT = atcoder::z_algorithm(t);
        for (int p = 1; p <= n; p++) {
            int a = p == n ? p : min(ZS[p] + p, n);
            int b = min(ZT[n + m - p], m);
            if (a + b < 2 * p) continue;
            res.emplace_back(p, a, b);
        }
        return res;
    };
    auto dfs = [&](auto rc, int L, int R) -> void {
        if (R - L <= 1) return;
        int M = (L + R) / 2;
        rc(rc, L, M), rc(rc, M, R);
        C SL{begin(S) + L, begin(S) + M};
        C SR{begin(S) + M, begin(S) + R};
        auto sub_res1 = solve_sub(SL, SR);
        for (auto& [p, a, b] : sub_res1) by_p[p].emplace_back(M - a, M + b);
        reverse(begin(SL), end(SL));
        reverse(begin(SR), end(SR));
        auto sub_res2 = solve_sub(SR, SL);
        for (auto& [p, a, b] : sub_res2) by_p[p].emplace_back(M - b, M + a);
    };
    dfs(dfs, 0, N);
    vector<T> res;
    set<pair<int, int>> done;
    for (int p = 0; p <= N; p++) {
        auto& LR = by_p[p];
        sort(begin(LR), end(LR), [](auto& x, auto& y) {
                if (x.first == y.first) return x.second > y.second;
                return x.first < y.first;
                });
        int r = -1;
        for (auto& lr : LR) {
            if (r >= lr.second) continue;
            r = lr.second;
            if (!done.count(lr)) {
                done.insert(lr);
                res.emplace_back(p, lr.first, lr.second);
            }
        }
    }
    return res;
}
struct MINstack{
    vector<pair<int,int> >dat;
    void add(int idx,int len)
    {
        while(!dat.empty()&&dat.back().second>=len)dat.pop_back();
        dat.push_back(make_pair(idx,len));
    }
    int get(int idx)
    {
        assert(!dat.empty());
        int ret=dat[0].first;
        int v=1,off=1;
        while(v<=idx-ret)v*=10,off++;
        int val=dat[0].second+off;
        auto it=dat.begin();
        while(v>=10)
        {
            v/=10;
            off--;
            it=lower_bound(it,dat.end(),make_pair(idx-v+1,0));
            if(it==dat.end())break;
            if(val>it->second+off)val=it->second+off,ret=it->first;
        }
        return idx-ret;
    }
};
string S;
int dp[5<<17];
pair<int,int>ppe[5<<17];
void solve()
{
    vector<tuple<int,int,int> >run=run_enumerate(S);
    vector<vector<MINstack> >dat(run.size());
    vector<vector<int> >ask(S.size()+1);
    for(int i=0;i<run.size();i++)
    {
        auto[p,l,r]=run[i];
        assert(r-l>=2*p);
        int need=min(p,r-l-2*p+1);
        dat[i].resize(need);
        for(int k=l+2*p;k<=r;k++)ask[k].push_back(i);
    }
    dp[0]=0;
    int one_parent=0;
    for(int i=1;i<=S.size();i++)
    {
        {//period * 1
            if(dp[one_parent]+i-one_parent+1>dp[i-1]+2)one_parent=i-1;
            dp[i]=dp[one_parent]+i-one_parent+1;
            ppe[i]=make_pair(i-one_parent,1);
        }
        for(int ri:ask[i])
        {
            auto[p,l,r]=run[ri];
            int idx=(i-l)%p;
            assert(idx<dat[ri].size());
            int pr=(i-l)/p;
            dat[ri][idx].add(pr-2,dp[i-2*p]);
            int pqr=dat[ri][idx].get(pr);
            int keta=0;
            {
                int v=pqr;
                while(v)v/=10,keta++;
            }
            if(dp[i]>dp[i-p*pqr]+p+keta)
            {
                dp[i]=dp[i-p*pqr]+p+keta;
                ppe[i]=make_pair(p,pqr);
            }
        }
    }
    vector<pair<string,int> >ans;
    int idx=S.size();
    while(idx>0)
    {
        auto[p,len]=ppe[idx];
        ans.push_back(make_pair(S.substr(idx-p,p),len));
        idx-=p*len;
    }
    for(int i=ans.size();i--;)cout<<ans[i].first<<ans[i].second;
    cout<<"\n";
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;cin>>T;
    for(;T--;)
    {
        cin>>S;
        solve();
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0