結果

問題 No.2162 Copy and Paste 2
ユーザー norikame
提出日時 2022-12-13 22:27:14
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,147 bytes
コンパイル時間 5,814 ms
コンパイル使用メモリ 323,496 KB
実行使用メモリ 74,960 KB
最終ジャッジ日時 2024-11-07 16:12:22
合計ジャッジ時間 14,845 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 3 TLE * 1 -- * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

// 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;

using ll = long long;

#define rep(i, n) for (int i=0; i<(int)(n); ++(i))
#define rep3(i, m, n) for (int i=(m); (i)<(int)(n); ++(i))
#define repr(i, n) for (int i=(int)(n)-1; (i)>=0; --(i))
#define rep3r(i, m, n) for (int i=(int)(n)-1; (i)>=(int)(m); --(i))
#define all(x) (x).begin(), (x).end()

const int INF = (int)(1e9);

int main() {
	string s;
	cin >> s;
	int n = s.length();
	auto za = z_algorithm(s);
	rep(i, n) za[i] = min(za[i], i);
	repr(i, n) za[i] -= n-i;
	map<int, set<int>> vids;
	rep(i, n) vids[za[i]].insert(-i);
	vector<unordered_map<int, int>> memo(n);
	auto calc = [&](auto calc, int id, int ri) -> int {
		if (id < 0) return 0;
		if (ri > id+1) return INF;
		if (memo[id].find(ri) != memo[id].end()) return memo[id][ri];
		if (id == 0) return memo[id][ri] = 1;
		else if (ri == 0) {
			int vid = -(n-1-id), rval = calc(calc, id-1, ri) + 1;
			auto sitr = vids.lower_bound(vid);
			while (sitr!=vids.end() && sitr->second.upper_bound(-id)!=sitr->second.end()) {
				auto itr = sitr->second.upper_bound(-id);
				while (itr != sitr->second.end()) {
					int ti = -(*itr), len = id - ti + 1;
					rval = min(rval, calc(calc, ti-1, len)+1);
					++itr;
				}
				++sitr;
			}
			return memo[id][ri] = rval;
		}
		else if (id+1 == ri) {
			int vid = -(n-1-id), rval = calc(calc, id-1, 0) + 2;
			auto sitr = vids.lower_bound(vid);
			while (sitr!=vids.end() && sitr->second.upper_bound(-id)!=sitr->second.end()) {
				auto itr = sitr->second.upper_bound(-id);
				while (itr != sitr->second.end()) {
					int ti = -(*itr), len = id - ti + 1;
					rval = min(rval, calc(calc, ti-1, len)+2);
					++itr;
				}
				++sitr;
			}
			return memo[id][ri] = rval;
		}
		else {
			int vid = -(n-1-id), rval = calc(calc, id-1, ri) + 1;
			auto sitr = vids.lower_bound(vid);
			while (sitr != vids.end()) {
				if (sitr->second.find(-(id-ri+1)) != sitr->second.end()) {
					rval = min(rval, calc(calc, id-ri, ri)+1);
					break;
				}
				++sitr;
			}
			return memo[id][ri] = rval;
		}
	};
	cout << calc(calc, n-1, 0) << endl;
	return 0;
}
0