結果
| 問題 | No.2204 Palindrome Splitting (No Rearrangement ver.) |
| ユーザー |
👑  Kazun
|
| 提出日時 | 2023-02-04 01:25:50 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 1,034 ms / 2,000 ms |
| コード長 | 5,663 bytes |
| コンパイル時間 | 174 ms |
| コンパイル使用メモリ | 82,204 KB |
| 実行使用メモリ | 77,260 KB |
| 最終ジャッジ日時 | 2024-07-02 23:20:37 |
| 合計ジャッジ時間 | 27,811 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 41 ms
53,248 KB |
| testcase_01 | AC | 44 ms
53,760 KB |
| testcase_02 | AC | 47 ms
54,528 KB |
| testcase_03 | AC | 620 ms
76,628 KB |
| testcase_04 | AC | 212 ms
77,060 KB |
| testcase_05 | AC | 154 ms
76,404 KB |
| testcase_06 | AC | 1,010 ms
76,748 KB |
| testcase_07 | AC | 908 ms
76,572 KB |
| testcase_08 | AC | 829 ms
77,184 KB |
| testcase_09 | AC | 866 ms
76,580 KB |
| testcase_10 | AC | 1,006 ms
77,256 KB |
| testcase_11 | AC | 829 ms
76,544 KB |
| testcase_12 | AC | 999 ms
76,544 KB |
| testcase_13 | AC | 1,016 ms
76,800 KB |
| testcase_14 | AC | 1,004 ms
76,836 KB |
| testcase_15 | AC | 929 ms
76,648 KB |
| testcase_16 | AC | 434 ms
76,316 KB |
| testcase_17 | AC | 544 ms
76,672 KB |
| testcase_18 | AC | 1,003 ms
76,516 KB |
| testcase_19 | AC | 1,007 ms
76,416 KB |
| testcase_20 | AC | 1,005 ms
76,672 KB |
| testcase_21 | AC | 1,005 ms
77,056 KB |
| testcase_22 | AC | 1,003 ms
76,800 KB |
| testcase_23 | AC | 1,008 ms
76,824 KB |
| testcase_24 | AC | 1,003 ms
76,392 KB |
| testcase_25 | AC | 1,009 ms
76,368 KB |
| testcase_26 | AC | 1,005 ms
76,768 KB |
| testcase_27 | AC | 682 ms
76,800 KB |
| testcase_28 | AC | 1,010 ms
76,424 KB |
| testcase_29 | AC | 1,004 ms
77,260 KB |
| testcase_30 | AC | 41 ms
52,992 KB |
| testcase_31 | AC | 43 ms
53,888 KB |
| testcase_32 | AC | 1,034 ms
76,620 KB |
| testcase_33 | AC | 1,008 ms
76,484 KB |
| testcase_34 | AC | 41 ms
53,376 KB |
| testcase_35 | AC | 1,034 ms
77,216 KB |
ソースコード
class Rolling_Hash():
def __init__(self,S, base, mod, type=0):
""" type=0: 整数列 (各要素は mod 未満), type=1: 文字列 (mod>(最大の文字コード))
"""
self.mod=mod
self.base=base
self.length=len(S)
self.power=power=[1]*(len(S)+1)
self.type=type
L=len(S)
self.hash=h=[0]*(L+1)
for i in range(L):
if type:
h[i+1]=(base*h[i]+ord(S[i]))%mod
else:
h[i+1]=(base*h[i]+S[i])%mod
for i in range(L):
power[i+1]=base*power[i]%mod
def __hasher(self, X):
assert len(X)<=len(self)
h=0
for i in range(len(X)):
h=(h*self.base+X[i])%self.mod
return h
def get(self, l, r):
return (self.hash[r]-self.hash[l]*self.power[r-l])%self.mod
def count(self, T, start=0):
alpha=self.__hasher(T)
K=0
for i in range(start, len(self)-len(T)+1):
if alpha==self[i: i+len(T)]:
K+=1
return K
def find(self, T, start=0):
alpha=self.__hasher(T)
for i in range(start, len(self)-len(T)+1):
if alpha==self[i: i+len(T)]:
return i
return -1
def rfind(self, T, start=0):
alpha=self.__hasher(T)
for i in range(len(self)-len(T), start-1, -1):
if alpha==self[i: i+len(T)]:
return i
return -1
def index(self, T, start=0):
alpha=self.__hasher(T)
for i in range(start, len(self)-len(T)+1):
if alpha==self[i: i+len(T)]:
return i
raise ValueError("substring not found")
def __getitem__(self, index):
if index.__class__==int:
if index<0:
index+=self.length
assert 0<=index<self.length
return self.get(index, index+1)
elif index.__class__==slice:
assert (index.step==None) or (index.step==1)
L=index.start if index.start else 0
R=index.stop if index.stop else len(self)
if L<0:
L+=len(self)
if R<0:
R+=len(self)
return self.get(L,R)
def __len__(self):
return self.length
def docking(self, l0, r0, l1, r1):
""" [l0, r0) と [l1, r1) の部分列をドッキングしたハッシュを返す.
"""
h0=self.get(l0,r0); h1=self.get(l1,r1)
return (h0*self.power[r1-l1]+h1)%self.mod
#=================================================
class Double_Rolling_Hash():
def __init__(self, S, base, mod0, mod1, type):
self.__length=len(S)
self.__base=base
self.__mod0=mod0
self.__mod1=mod1
self.__type=type
self.rh0=Rolling_Hash(S, base, mod0, type)
self.rh1=Rolling_Hash(S, base, mod1, type)
def encode(self, a0, a1):
return a0*self.__mod1+a1
def get(self, l, r):
a0=self.rh0.get(l,r)
a1=self.rh1.get(l,r)
return self.encode(a0,a1)
def __hasher(self, X):
assert len(X)<=len(self)
a0=0; a1=0
for x in X:
if self.__type==0:
a0=(a0*self.__base+x)%self.__mod0
a1=(a1*self.__base+x)%self.__mod1
return self.encode(a0,a1)
def __getitem__(self, index):
if index.__class__==int:
if index<0:
index+=self.__length
assert 0<=index<self.__length
return self.encode(self.rh0[index], self.rh1[index])
elif index.__class__==slice:
assert (index.step==None) or (index.step==1)
L=index.start if index.start else 0
R=index.stop if index.stop else len(self)
if L<0:
L+=len(self)
if R<0:
R+=len(self)
return self.encode(self.rh0[L: R], self.rh1[L: R])
def count(self, T, start=0):
alpha=self.__hasher(T)
K=0
T_len=len(T)
for i in range(start, len(self)-len(T)+1):
if alpha==self[i: i+T_len]:
K+=1
return K
def find(self, T, start=0):
alpha=self.__hasher(T)
for i in range(start, len(self)-len(T)+1):
if alpha==self[i: i+len(T)]:
return i
return -1
def rfind(self, T, start=0):
alpha=self.__hasher(T)
for i in range(len(self)-len(T), start-1, -1):
if alpha==self[i: i+len(T)]:
return i
return -1
def index(self, T, start=0):
alpha=self.__hasher(T)
for i in range(start, len(self)-len(T)+1):
if alpha==self[i: i+len(T)]:
return i
raise ValueError("substring not found")
def __len__(self):
return self.__length
def docking(self, l0, r0, l1, r1):
""" ranges: tuple (l,r) からなるリスト, i 番目の (l,r) は部分列 [l,r) を意味する.
"""
return self.encode(self.rh0.docking(l0, r0, l1, r1), self.rh1.docking(l0, r0, l1, r1))
#==================================================
def solve():
S=input(); N=len(S)
Mod0=10**9+7; Mod1=10**9+9
SHo=Double_Rolling_Hash("*"+S, 100, Mod0, Mod1, 1)
SHr=Double_Rolling_Hash("*"+S[::-1], 100, Mod0, Mod1, 1)
inf=N+1
DP=[-inf]*(N+1); DP[0]=inf
for i in range(1,N+1):
for j in range(1,i+1):
length=i-j+1
if SHo[j:i+1]==SHr[N-i+1:N-j+1+1]:
DP[i]=max(DP[i], min(length, DP[j-1]))
return DP[N]
#==================================================
print(solve())