提出 #27208776

ソースコード 拡げる

# dp[x][e][y]=(i番目まで見て、)swapをx回していて、Eをe個、Yをy個使用済みのとき、(残りの文字列,数)
from collections import defaultdict
S=list(input())
K=int(input())
def fix():return defaultdict(fix)
dp=defaultdict(fix)
dp[0][0][0]=(S,1)

for _ in range(len(S)):
	new_dp=defaultdict(fix)
	for x,d1 in dp.items():
		for e,d2 in d1.items():
			for y,(s,val) in d2.items():
				for c in "KEY":
					if c in s:
						idx=s.index(c)
						xx=x+idx
						ee=e+(c=='E')
						yy=y+(c=='Y')
						if yy in new_dp[xx][ee]:
							new_dp[xx][ee][yy]=(new_dp[xx][ee][yy][0], new_dp[xx][ee][yy][1]+val)
						else:
							new_dp[xx][ee][yy]=(s[:idx]+s[idx+1:], val)
	dp=new_dp

ans=0
for x,d1 in dp.items():
	if x>K:continue
	for e,d2 in d1.items():
		for y,(s,val) in d2.items():
			ans+=val
print(ans)

提出情報

提出日時
問題 E - Swap
ユーザ kyopro_friends
言語 Python (3.8.2)
得点 500
コード長 855 Byte
結果 AC
実行時間 331 ms
メモリ 14324 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 500 / 500
結果
AC × 3
AC × 37
セット名 テストケース
Sample sample_01.txt, sample_02.txt, sample_03.txt
All random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, random_26.txt, random_27.txt, random_28.txt, random_29.txt, random_30.txt, random_31.txt, random_32.txt, random_33.txt, random_34.txt, sample_01.txt, sample_02.txt, sample_03.txt
ケース名 結果 実行時間 メモリ
random_01.txt AC 201 ms 12088 KiB
random_02.txt AC 24 ms 9184 KiB
random_03.txt AC 224 ms 12352 KiB
random_04.txt AC 22 ms 9292 KiB
random_05.txt AC 202 ms 11976 KiB
random_06.txt AC 25 ms 9228 KiB
random_07.txt AC 213 ms 12500 KiB
random_08.txt AC 40 ms 9592 KiB
random_09.txt AC 225 ms 12816 KiB
random_10.txt AC 72 ms 10296 KiB
random_11.txt AC 207 ms 12412 KiB
random_12.txt AC 34 ms 9456 KiB
random_13.txt AC 218 ms 12508 KiB
random_14.txt AC 41 ms 9512 KiB
random_15.txt AC 165 ms 11444 KiB
random_16.txt AC 173 ms 11948 KiB
random_17.txt AC 251 ms 13156 KiB
random_18.txt AC 46 ms 9672 KiB
random_19.txt AC 220 ms 12504 KiB
random_20.txt AC 29 ms 9540 KiB
random_21.txt AC 201 ms 12104 KiB
random_22.txt AC 97 ms 10844 KiB
random_23.txt AC 232 ms 13164 KiB
random_24.txt AC 112 ms 10920 KiB
random_25.txt AC 20 ms 9348 KiB
random_26.txt AC 19 ms 9348 KiB
random_27.txt AC 231 ms 12816 KiB
random_28.txt AC 161 ms 11708 KiB
random_29.txt AC 195 ms 12140 KiB
random_30.txt AC 227 ms 12936 KiB
random_31.txt AC 331 ms 14324 KiB
random_32.txt AC 225 ms 12628 KiB
random_33.txt AC 324 ms 14136 KiB
random_34.txt AC 22 ms 9288 KiB
sample_01.txt AC 21 ms 9476 KiB
sample_02.txt AC 29 ms 9176 KiB
sample_03.txt AC 21 ms 9304 KiB