#837488 (C++14) No.2204 Palindrome Splitting (No Rearrangement ver.)

提出ソース

結果

問題	No.2204 Palindrome Splitting (No Rearrangement ver.)
ユーザー	woodywoody
提出日時	2023-02-04 05:27:00
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	399 ms / 2,000 ms
コード長	7,808 bytes
コンパイル時間	4,606 ms
コンパイル使用メモリ	245,052 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-07-03 03:37:15
合計ジャッジ時間	15,043 ms
ジャッジサーバーID （参考情報）	judge2 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	214 ms 5,376 KB
testcase_04	AC	52 ms 5,376 KB
testcase_05	AC	30 ms 5,376 KB
testcase_06	AC	389 ms 5,376 KB
testcase_07	AC	342 ms 5,376 KB
testcase_08	AC	317 ms 5,376 KB
testcase_09	AC	342 ms 5,376 KB
testcase_10	AC	383 ms 5,376 KB
testcase_11	AC	311 ms 5,376 KB
testcase_12	AC	394 ms 5,376 KB
testcase_13	AC	384 ms 5,376 KB
testcase_14	AC	399 ms 5,376 KB
testcase_15	AC	356 ms 5,376 KB
testcase_16	AC	150 ms 5,376 KB
testcase_17	AC	194 ms 5,376 KB
testcase_18	AC	391 ms 5,376 KB
testcase_19	AC	382 ms 5,376 KB
testcase_20	AC	391 ms 5,376 KB
testcase_21	AC	388 ms 5,376 KB
testcase_22	AC	391 ms 5,376 KB
testcase_23	AC	387 ms 5,376 KB
testcase_24	AC	389 ms 5,376 KB
testcase_25	AC	399 ms 5,376 KB
testcase_26	AC	391 ms 5,376 KB
testcase_27	AC	254 ms 5,376 KB
testcase_28	AC	390 ms 5,376 KB
testcase_29	AC	391 ms 5,376 KB
testcase_30	AC	2 ms 5,376 KB
testcase_31	AC	2 ms 5,376 KB
testcase_32	AC	293 ms 5,376 KB
testcase_33	AC	380 ms 5,376 KB
testcase_34	AC	2 ms 5,376 KB
testcase_35	AC	298 ms 5,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include<bits/stdc++.h>
#include<atcoder/all>
#define rep(i,b) for(int i=0;i<b;i++)
#define rrep(i,b) for(int i=b-1;i>=0;i--)
#define rep1(i,b) for(int i=1;i<b;i++)
#define repx(i,x,b) for(int i=x;i<b;i++)
#define rrepx(i,x,b) for(int i=b-1;i>=x;i--)
#define fore(i,a) for(auto i:a)
#define fore1(i,a) for(auto &i:a)
#define rng(x) (x).begin(), (x).end()
#define rrng(x) (x).rbegin(), (x).rend()
#define sz(x) ((int)(x).size())
#define pb push_back
#define fi first
#define se second
#define pcnt __builtin_popcountll

using namespace std;
using namespace atcoder;

using ll = long long;
using ld = long double;
template<typename T> using mpq = priority_queue<T, vector<T>, greater<T>>;
template<typename T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<typename T> bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<typename T> ll sumv(const vector<T>&a){ll res(0);for(auto&&x:a)res+=x;return res;}
bool yn(bool a) { if(a) {cout << "Yes" << endl; return true;} else {cout << "No" << endl; return false;}}
#define dame { cout << "No" << endl; return;}
#define dame1 { cout << -1 << endl; return;}
#define cout2(x,y) cout << x << " " << y << endl;
#define coutp(p) cout << p.fi << " " << p.se << endl;
#define out cout << ans << endl;
#define outd cout << fixed << setprecision(20) << ans << endl;
#define outm cout << ans.val() << endl;
#define outv fore(yans , ans) cout << yans << "\n";
#define outdv fore(yans , ans) cout << yans.val() << "\n";
#define coutv(v) {fore(vy , v) {cout << vy << " ";} cout << endl;}
#define coutv2(v) fore(vy , v) cout << vy << "\n";
#define coutvm(v) {fore(vy , v) {cout << vy.val() << " ";} cout << endl;}
#define coutvm2(v) fore(vy , v) cout << vy.val() << "\n";
using pll = pair<ll,ll>;using pil = pair<int,ll>;using pli = pair<ll,int>;using pii = pair<int,int>;using pdd = pair<ld,ld>;
using tp = tuple<int ,int ,int>;
using vi = vector<int>;using vd = vector<ld>;using vl = vector<ll>;using vs = vector<string>;using vb = vector<bool>;
using vpii = vector<pii>;using vpli = vector<pli>;using vpll = vector<pll>;using vpil = vector<pil>;
using vvi = vector<vector<int>>;using vvl = vector<vector<ll>>;using vvs = vector<vector<string>>;using vvb = vector<vector<bool>>;
using vvpii = vector<vector<pii>>;using vvpli = vector<vector<pli>>;using vvpll = vector<vpll>;using vvpil = vector<vpil>;
using mint = modint998244353;
//using mint = modint1000000007;
//using mint = dynamic_modint<0>;
using vm = vector<mint>;
using vvm = vector<vector<mint>>;
vector<int> dx={1,0,-1,0,1,1,-1,-1},dy={0,1,0,-1,1,-1,1,-1};
ll gcd(ll a, ll b) { return a?gcd(b%a,a):b;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}
#define yes {cout <<"Yes"<<endl;}
#define yesr { cout <<"Yes"<<endl; return;}
#define no {cout <<"No"<<endl;}
#define nor { cout <<"No"<<endl; return;}
const double eps = 1e-10;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
#ifdef MY_LOCAL_DEBUG
#define show(x) cerr<<#x<<" = "<<x<<endl
#define showp(p) cerr<<#p<<" = "<<p.fi<<" : "<<p.se<<endl
#define show2(x,y) cerr<<#x<<" = "<<x<<" : "<<#y<<" = "<<y<<endl
#define show3(x,y,z) cerr<<#x<<" = "<<x<<" : "<<#y<<" = "<<y<<" : "<<#z<<" = "<<z<<endl
#define show4(x,y,z,x2) cerr<<#x<<" = "<<x<<" : "<<#y<<" = "<<y<<" : "<<#z<<" = "<<z<<" : "<<#x2<<" = "<<x2<<endl
#define test(x) cout << "test" << x << endl
#define showv(v) {fore(vy , v) {cout << vy << " ";} cout << endl;}
#define showv2(v) fore(vy , v) cout << vy << "\n";
#define showvm(v) {fore(vy , v) {cout << vy.val() << " ";} cout << endl;}
#define showvm2(v) fore(vy , v) cout << vy.val() << "\n";
#else
#define show(x)
#define showp(p)
#define show2(x,y)
#define show3(x,y,z)
#define show4(x,y,z,x2)
#define test(x)
#define showv(v)
#define showv2(v)
#define showvm(v)
#define showvm2(v)
#endif

using ull = uint64_t;
		
struct RollingHashSystem{
	const ull MASK30 = (1UL << 30) - 1;
	const ull MASK31 = (1UL << 31) - 1;
	const ull MOD = ((ull)1 << 61) - 1;
	const ull MASK61 = MOD;
	vector<ull> CharHash; //英小文字ーhash
	unordered_map<ull,int> idx; //hash-index(挿入順番号)
	int str_num = 0; //挿入した文字列の総数
	ull Base; //基底

	RollingHashSystem(){
		map<ull,int> tmp;
		CharHash = vector<ull>(26);
		ull mx = 0;
		srand(time(NULL));
		rep(i,26){
			ull y = rand()+1;
			while(tmp.count(y)){
				y = rand()+1;
			}
			tmp[y] = 0;
			CharHash[i] = y;
			chmax(mx,y);
		}
	
		ull base_tmp = 37;
		while(1){
			int k = rand()+1;
			if (gcd(MOD,k) != 1) continue;
			Base = PowMod(base_tmp , k);
			if (Base <= mx) continue;
			break;
		}
	};
	//a*b mod 2^61-1を返す関数(最後にModを取る)
	ull Mul(ull a, ull b)
	{
		a = (a + MOD) % MOD;
		b = (b + MOD) % MOD;
		ull au = a >> 31;
		ull ad = a & MASK31;
		ull bu = b >> 31;
		ull bd = b & MASK31;
		ull mid = ad * bu + au * bd;
		ull midu = mid >> 30;
		ull midd = mid & MASK30;
		return CalcMod(au * bu * 2 + midu + (midd << 31) + ad * bd);
	}
	//mod 2^61-1を計算する関数
	ull CalcMod(ull x)
	{
		ull xu = x >> 61;
		ull xd = x & MASK61;
		ull res = xu + xd;
		if (res >= MOD) res -= MOD;
		return res;
	}
	ull PowMod(ull base, ull exp) { // base^exp mod MOD
		if (exp == 0) {
			return 1;
		} else if (exp % 2 == 0) {
			ull t = PowMod(base, exp / 2);
			return Mul(t, t);
		} else {
			return Mul(base, PowMod(base, exp - 1));
		}
	}
	ull GetHash(string s){ // 文字列sのhashを取得
		ull now = 0;
		int n = sz(s);
		rrep(i,n){
			now = Mul(now,Base) + CharHash[s[i]-'a'];
		}
		return now;
	}
	ull Apply(string s){ // 文字列sにhashを割り当て保存
		ull hash = GetHash(s);
		idx[hash] = str_num;
		str_num++;
		return hash;
	}
	int GetIdx(string s){ // 文字列sの挿入順番号を取得
		ull hash = GetHash(s);
		int ret = -1;
		if (idx.count(hash)) ret = idx[hash];
		return ret;
	}
	int GetIdx(ull hash){ // hashをもつ文字列のidxを取得
		int ret = -1;
		if (idx.count(hash)) ret = idx[hash];
		return ret;
	}
}RHS;

struct RH{
	vector<ull> hashed, power;//1-indexed
	string s;
	int n;
	RH(string s_) : s(s_){
		n = sz(s);
		hashed = vector<ull>(n+1,0); power = vector<ull>(n+1,0);
		power[0] = 1;
		rep(i,n){
			power[i+1] = RHS.Mul(power[i], RHS.Base); 
			hashed[i+1] = RHS.Mul(hashed[i],RHS.Base) + RHS.CharHash[s[i]-'a'];
			if (hashed[i+1] >= RHS.MOD) hashed[i+1] -= RHS.MOD;
		}
	};
	ull get(ull l, ull r) const {// [l,r)のhash取得
		ull ret = hashed[r] + RHS.MOD - RHS.Mul(hashed[l], power[r - l]);
		if(ret >= RHS.MOD) ret -= RHS.MOD;
		return ret;
	}
	ull connect(ull h1, ull h2, ull h2len) const {
		ull ret = RHS.Mul(h1, power[h2len]) + h2;
		if(ret >= RHS.MOD) ret -= RHS.MOD;
		return ret;
	}
	void connect(const string &s){
		int n = hashed.size() - 1, m = s.size();
		hashed.resize(n + m + 1);
		power.resize(n + m + 1);
		for(int i = n; i < n + m; i++) {
			power[i + 1] = RHS.Mul(power[i], RHS.Base);
			hashed[i + 1] = RHS.Mul(hashed[i], RHS.Base) + RHS.CharHash[s[i]-'a'];
			if(hashed[i + 1] >= RHS.MOD) hashed[i + 1] -= RHS.MOD;
		}
	}
	ull LCP(const RH &b, int l1, int r1, int l2, int r2) {
		int len = min(r1 - l1, r2 - l2);
		int low = -1, high = len + 1;
		while(high - low > 1) {
			int mid = (low + high) / 2;
			if(get(l1, l1 + mid) == b.get(l2, l2 + mid)) low = mid;
			else high = mid;
		}
		return low;
	}
};

void solve(){
	string s; cin>>s;
	string t = s;
	reverse(rng(t));
	RH l(s),r(t);
	int n = sz(s);
	vi dp(n);
	rep(i,n){
		if (i == 0){
			repx(j,i,n){
				if (l.get(i,j+1)==r.get(n-j-1,n-i)){
					chmax(dp[j],j-i+1);
				}
			}
		}else{
			repx(j,i,n){
				if (l.get(i,j+1)==r.get(n-j-1,n-i)){
					chmax(dp[j],min(j-i+1,dp[i-1]));
				}
			}
		}
	}
	cout << dp[n-1] << endl;

	return;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	int t = 1;
	//cin>>t;

	rep(i,t){
		solve();
	}

	return 0;
}

yukicoder

結果

テストケース

ソースコード