#1033167 (C++23) No.3000 Optimal Run Length Encoding

• 問題: 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

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	230 ms; 5,248 KB
testcase_02	AC	221 ms; 5,248 KB
testcase_03	AC	212 ms; 5,248 KB
testcase_04	AC	245 ms; 5,248 KB
testcase_05	AC	205 ms; 5,248 KB
testcase_06	AC	205 ms; 5,248 KB
testcase_07	AC	219 ms; 5,248 KB
testcase_08	AC	216 ms; 5,248 KB
testcase_09	AC	213 ms; 5,248 KB
testcase_10	AC	197 ms; 5,248 KB
testcase_11	AC	209 ms; 5,248 KB
testcase_12	AC	211 ms; 5,248 KB
testcase_13	AC	218 ms; 5,248 KB
testcase_14	AC	193 ms; 5,248 KB
testcase_15	AC	203 ms; 5,248 KB
testcase_16	AC	216 ms; 5,248 KB
testcase_17	AC	190 ms; 5,248 KB
testcase_18	AC	133 ms; 5,248 KB
testcase_19	AC	374 ms; 5,248 KB
testcase_20	AC	341 ms; 5,248 KB
testcase_21	AC	336 ms; 5,248 KB
testcase_22	AC	335 ms; 5,248 KB
testcase_23	AC	336 ms; 5,248 KB
testcase_24	AC	323 ms; 5,248 KB
testcase_25	AC	333 ms; 5,248 KB
testcase_26	AC	331 ms; 5,248 KB
testcase_27	AC	298 ms; 5,248 KB
testcase_28	AC	328 ms; 5,248 KB
testcase_29	AC	357 ms; 5,248 KB
testcase_30	AC	426 ms; 5,248 KB
testcase_31	AC	433 ms; 5,248 KB
testcase_32	AC	501 ms; 5,248 KB
testcase_33	AC	544 ms; 5,248 KB
testcase_34	AC	680 ms; 16,436 KB
testcase_35	AC	441 ms; 26,312 KB
testcase_36	AC	430 ms; 26,440 KB
testcase_37	AC	436 ms; 26,188 KB
testcase_38	AC	427 ms; 26,184 KB
testcase_39	AC	450 ms; 26,316 KB
testcase_40	AC	478 ms; 26,316 KB
testcase_41	AC	427 ms; 26,188 KB
testcase_42	AC	426 ms; 26,188 KB
testcase_43	AC	426 ms; 26,320 KB
testcase_44	AC	435 ms; 26,316 KB
testcase_45	AC	2,673 ms; 327,028 KB
testcase_46	AC	1,843 ms; 271,588 KB
testcase_47	AC	2,320 ms; 295,604 KB
testcase_48	AC	1,890 ms; 282,008 KB
testcase_49	AC	2,100 ms; 287,296 KB
testcase_50	AC	1,919 ms; 287,588 KB
testcase_51	AC	2,252 ms; 289,876 KB
testcase_52	AC	2,026 ms; 292,112 KB
testcase_53	AC	2,230 ms; 294,244 KB
testcase_54	AC	1,729 ms; 265,484 KB
testcase_55	AC	2,465 ms; 326,900 KB
testcase_56	AC	2,092 ms; 293,516 KB
testcase_57	AC	2,177 ms; 276,280 KB
testcase_58	AC	1,798 ms; 272,052 KB
testcase_59	AC	2,658 ms; 307,360 KB
testcase_60	AC	2,734 ms; 326,900 KB
testcase_61	AC	2,504 ms; 309,832 KB
testcase_62	AC	1,851 ms; 275,900 KB
testcase_63	AC	2,336 ms; 290,376 KB
testcase_64	AC	1,767 ms; 271,596 KB
testcase_65	AC	897 ms; 75,492 KB
testcase_66	AC	550 ms; 36,896 KB
testcase_67	AC	887 ms; 57,548 KB
testcase_68	AC	540 ms; 35,000 KB
testcase_69	AC	989 ms; 81,684 KB
testcase_70	AC	1,613 ms; 113,140 KB
testcase_71	AC	514 ms; 27,820 KB
testcase_72	AC	1,092 ms; 58,556 KB
testcase_73	AC	552 ms; 40,140 KB
testcase_74	AC	934 ms; 61,536 KB
testcase_75	AC	483 ms; 39,592 KB
testcase_76	AC	919 ms; 61,036 KB
testcase_77	AC	519 ms; 37,792 KB
testcase_78	AC	867 ms; 60,996 KB
testcase_79	AC	504 ms; 39,368 KB
testcase_80	AC	777 ms; 53,128 KB
testcase_81	AC	74 ms; 5,248 KB
testcase_82	AC	1,194 ms; 71,892 KB
testcase_83	AC	1,233 ms; 71,452 KB
testcase_84	AC	1,240 ms; 71,544 KB
testcase_85	AC	1,226 ms; 70,364 KB
testcase_86	AC	1,168 ms; 67,792 KB
testcase_87	AC	1,273 ms; 75,260 KB
testcase_88	AC	1,172 ms; 68,956 KB
testcase_89	AC	1,246 ms; 75,260 KB
testcase_90	AC	1,122 ms; 65,760 KB
testcase_91	AC	1,148 ms; 67,184 KB
testcase_92	AC	1,203 ms; 71,088 KB
testcase_93	AC	1,197 ms; 70,984 KB
testcase_94	AC	1,212 ms; 71,240 KB
testcase_95	AC	1,191 ms; 71,000 KB
testcase_96	AC	1,451 ms; 70,892 KB
testcase_97	AC	524 ms; 27,616 KB
testcase_98	AC	349 ms; 23,256 KB
testcase_99	AC	329 ms; 20,944 KB
testcase_100	AC	384 ms; 25,024 KB
testcase_101	AC	427 ms; 26,400 KB
testcase_102	AC	512 ms; 33,468 KB
testcase_103	AC	523 ms; 34,676 KB
testcase_104	AC	590 ms; 38,900 KB
testcase_105	AC	535 ms; 37,016 KB
testcase_106	AC	570 ms; 37,172 KB
testcase_107	AC	503 ms; 37,984 KB
testcase_108	AC	623 ms; 36,228 KB
testcase_109	AC	516 ms; 34,448 KB
testcase_110	AC	552 ms; 38,828 KB
testcase_111	AC	629 ms; 40,880 KB
testcase_112	AC	888 ms; 54,360 KB
testcase_113	AC	908 ms; 54,180 KB
testcase_114	AC	903 ms; 54,288 KB
testcase_115	AC	906 ms; 54,324 KB
testcase_116	AC	888 ms; 55,348 KB
testcase_117	AC	884 ms; 54,744 KB
testcase_118	AC	1,052 ms; 54,296 KB
testcase_119	AC	1,067 ms; 55,348 KB
testcase_120	AC	1,065 ms; 54,792 KB
testcase_121	AC	905 ms; 55,188 KB
testcase_122	AC	909 ms; 54,668 KB
testcase_123	AC	925 ms; 55,060 KB
testcase_124	AC	885 ms; 54,876 KB
testcase_125	AC	922 ms; 52,404 KB
testcase_126	AC	913 ms; 57,304 KB
testcase_127	AC	904 ms; 54,604 KB
testcase_128	AC	941 ms; 52,608 KB
testcase_129	AC	903 ms; 52,080 KB
testcase_130	AC	908 ms; 54,120 KB
testcase_131	AC	913 ms; 52,192 KB
testcase_132	AC	1,397 ms; 90,196 KB
testcase_133	AC	1,323 ms; 88,516 KB
testcase_134	AC	1,321 ms; 86,936 KB
testcase_135	AC	1,310 ms; 84,484 KB
testcase_136	AC	1,266 ms; 80,528 KB
testcase_137	AC	1,274 ms; 80,132 KB
testcase_138	AC	1,270 ms; 79,592 KB
testcase_139	AC	1,272 ms; 78,736 KB
testcase_140	AC	1,256 ms; 78,044 KB
testcase_141	AC	1,267 ms; 76,928 KB
testcase_142	AC	1,250 ms; 75,400 KB

ソースコード

#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();
	}
}