結果

問題 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();
	}
}
0