結果

問題 No.3001 ヘビ文字列
ユーザー 👑 p-adicp-adic
提出日時 2024-12-29 14:53:01
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 919 ms / 1,500 ms
コード長 635 bytes
コンパイル時間 1,086 ms
コンパイル使用メモリ 82,340 KB
実行使用メモリ 160,944 KB
最終ジャッジ日時 2025-01-01 07:44:12
合計ジャッジ時間 49,512 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 37 ms
53,008 KB
testcase_01 AC 37 ms
53,344 KB
testcase_02 AC 38 ms
52,652 KB
testcase_03 AC 37 ms
52,340 KB
testcase_04 AC 38 ms
52,532 KB
testcase_05 AC 58 ms
66,780 KB
testcase_06 AC 57 ms
66,468 KB
testcase_07 AC 57 ms
65,884 KB
testcase_08 AC 57 ms
66,936 KB
testcase_09 AC 58 ms
66,828 KB
testcase_10 AC 58 ms
67,492 KB
testcase_11 AC 56 ms
66,304 KB
testcase_12 AC 58 ms
65,492 KB
testcase_13 AC 57 ms
66,768 KB
testcase_14 AC 58 ms
65,748 KB
testcase_15 AC 642 ms
160,536 KB
testcase_16 AC 627 ms
160,344 KB
testcase_17 AC 608 ms
160,516 KB
testcase_18 AC 634 ms
160,344 KB
testcase_19 AC 627 ms
160,872 KB
testcase_20 AC 759 ms
160,456 KB
testcase_21 AC 621 ms
160,456 KB
testcase_22 AC 630 ms
160,340 KB
testcase_23 AC 616 ms
160,820 KB
testcase_24 AC 609 ms
160,868 KB
testcase_25 AC 230 ms
151,180 KB
testcase_26 AC 232 ms
150,944 KB
testcase_27 AC 241 ms
150,804 KB
testcase_28 AC 231 ms
151,092 KB
testcase_29 AC 229 ms
150,780 KB
testcase_30 AC 231 ms
150,676 KB
testcase_31 AC 234 ms
151,112 KB
testcase_32 AC 228 ms
150,808 KB
testcase_33 AC 243 ms
150,692 KB
testcase_34 AC 242 ms
151,208 KB
testcase_35 AC 337 ms
144,868 KB
testcase_36 AC 332 ms
144,660 KB
testcase_37 AC 338 ms
144,540 KB
testcase_38 AC 328 ms
144,884 KB
testcase_39 AC 328 ms
144,796 KB
testcase_40 AC 329 ms
144,780 KB
testcase_41 AC 336 ms
144,788 KB
testcase_42 AC 335 ms
144,616 KB
testcase_43 AC 330 ms
144,500 KB
testcase_44 AC 336 ms
144,672 KB
testcase_45 AC 686 ms
159,276 KB
testcase_46 AC 678 ms
154,096 KB
testcase_47 AC 807 ms
158,536 KB
testcase_48 AC 919 ms
158,288 KB
testcase_49 AC 796 ms
158,636 KB
testcase_50 AC 785 ms
158,420 KB
testcase_51 AC 660 ms
153,828 KB
testcase_52 AC 639 ms
153,964 KB
testcase_53 AC 640 ms
153,920 KB
testcase_54 AC 639 ms
154,040 KB
testcase_55 AC 700 ms
156,276 KB
testcase_56 AC 703 ms
159,496 KB
testcase_57 AC 751 ms
159,080 KB
testcase_58 AC 704 ms
159,316 KB
testcase_59 AC 759 ms
159,032 KB
testcase_60 AC 734 ms
160,944 KB
testcase_61 AC 677 ms
160,768 KB
testcase_62 AC 725 ms
158,980 KB
testcase_63 AC 712 ms
157,724 KB
testcase_64 AC 730 ms
158,968 KB
testcase_65 AC 387 ms
131,172 KB
testcase_66 AC 430 ms
158,876 KB
testcase_67 AC 516 ms
142,376 KB
testcase_68 AC 344 ms
140,068 KB
testcase_69 AC 276 ms
112,200 KB
testcase_70 AC 467 ms
152,596 KB
testcase_71 AC 329 ms
126,556 KB
testcase_72 AC 360 ms
130,620 KB
testcase_73 AC 299 ms
117,924 KB
testcase_74 AC 442 ms
131,856 KB
testcase_75 AC 663 ms
154,188 KB
testcase_76 AC 671 ms
160,216 KB
testcase_77 AC 672 ms
160,260 KB
testcase_78 AC 705 ms
159,496 KB
testcase_79 AC 653 ms
153,920 KB
testcase_80 AC 627 ms
153,820 KB
testcase_81 AC 694 ms
159,860 KB
testcase_82 AC 680 ms
154,104 KB
testcase_83 AC 652 ms
160,020 KB
testcase_84 AC 696 ms
159,484 KB
testcase_85 AC 37 ms
53,500 KB
testcase_86 AC 38 ms
52,580 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

R=range
S=input()
N=len(S)
P=[];n=N
for i in R(2,int(n**0.5)+1):
	c=0
	while n%i<1:n//=i;c=1
	if c:P+=[i]
if n>1:P+=[n]
opt = N + 1
for p in P:
	d = N // p
	opt_temp = 0
	for i in R(d):
		h = [0]*26
		temp = 0
		for j in R(p):
			c = ord(S[i+j*d]) - ord('A')
			h[c] += 1
			temp = max( temp , h[c] )
		opt_temp += p - temp
	if opt > opt_temp:
		opt = opt_temp
		p_best = p
d = N // p_best
T=['A']*N
for i in R(d):
	h = [0]*26
	for j in R(p_best):h[ord(S[i+j*d]) - 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(p_best):T[i+j*d] = chr(c_opt + ord('A'))
print("".join(T))
0