結果

問題 No.2162 Copy and Paste 2
ユーザー norikamenorikame
提出日時 2022-12-13 22:27:14
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 2,147 bytes
コンパイル時間 6,029 ms
コンパイル使用メモリ 336,608 KB
実行使用メモリ 73,372 KB
最終ジャッジ日時 2024-04-25 06:05:08
合計ジャッジ時間 14,868 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 TLE -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
権限があれば一括ダウンロードができます

ソースコード

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