結果

問題 No.3001 ヘビ文字列
ユーザー 👑 p-adic
提出日時 2024-12-29 14:27:36
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 870 bytes
コンパイル時間 960 ms
コンパイル使用メモリ 82,084 KB
実行使用メモリ 238,400 KB
最終ジャッジ日時 2025-01-01 07:44:46
合計ジャッジ時間 117,845 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 43 TLE * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

R=range
S=input()
N=len(S)
L=1415
P=[]
C=[0]*L
for i in R(2,L):
	if C[i]<1:
		P+=[i];j=i*i
		while j<L:C[j],j=1,j+i
D=[1];E=[];e=n=N
for p in P:
	c=0
	while n%p<1:n//=p;c+=1
	r=len(D)
	for i in R(c):D+=[d*p for d in D[-r:]]
	if c:E+=[[p,c]];e=e//p*(p-1)
r=len(D)
if n>1:D+=[d*n for d in D[-r:]];r*=2;E+=[[n,1]];e=e//n*(n-1)
D.pop()
d_best = -1
opt = N + 1
for d in D:
	Nd = N // d
	opt_temp = 0
	for i in R(d):
		h = [0]*26
		temp = 0
		for j in R(Nd):
			c = ord(S[i+j*d]) - ord('A')
			h[c] += 1
			temp = max( temp , h[c] )
		opt_temp += Nd - temp
	if opt > opt_temp:
		opt = opt_temp
		d_best = d
Nd = N // d_best
T=['A']*N
for i in R(d_best):
	h = [0]*26
	for j in R(Nd):h[ord(S[i+j*d_best]) - ord('A')] += 1
	c_opt = -1
	temp = 0
	for c in R(26):
		if temp < h[c]:
			temp = h[c]
			c_opt = c
	for j in R(Nd):T[i+j*d_best] = chr(c_opt + ord('A'))
print("".join(T))
0