結果
問題 | No.1609 String Division Machine |
ユーザー | 👑 SPD_9X2 |
提出日時 | 2021-05-10 23:28:20 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
|
実行時間 | - |
コード長 | 2,260 bytes |
コンパイル時間 | 290 ms |
コンパイル使用メモリ | 87,096 KB |
実行使用メモリ | 146,936 KB |
最終ジャッジ日時 | 2023-09-20 12:33:10 |
合計ジャッジ時間 | 9,822 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 77 ms
71,592 KB |
testcase_01 | RE | - |
testcase_02 | AC | 75 ms
71,404 KB |
testcase_03 | AC | 75 ms
71,292 KB |
testcase_04 | AC | 76 ms
71,360 KB |
testcase_05 | AC | 76 ms
71,288 KB |
testcase_06 | AC | 76 ms
71,476 KB |
testcase_07 | AC | 87 ms
76,864 KB |
testcase_08 | AC | 87 ms
76,240 KB |
testcase_09 | AC | 77 ms
71,380 KB |
testcase_10 | AC | 75 ms
71,504 KB |
testcase_11 | AC | 85 ms
76,732 KB |
testcase_12 | RE | - |
testcase_13 | AC | 90 ms
76,760 KB |
testcase_14 | AC | 89 ms
76,764 KB |
testcase_15 | AC | 90 ms
76,620 KB |
testcase_16 | AC | 89 ms
76,740 KB |
testcase_17 | AC | 90 ms
76,744 KB |
testcase_18 | AC | 89 ms
76,532 KB |
testcase_19 | AC | 92 ms
76,776 KB |
testcase_20 | AC | 92 ms
76,780 KB |
testcase_21 | AC | 90 ms
76,620 KB |
testcase_22 | AC | 90 ms
76,696 KB |
testcase_23 | AC | 103 ms
76,756 KB |
testcase_24 | AC | 102 ms
76,660 KB |
testcase_25 | AC | 102 ms
76,636 KB |
testcase_26 | AC | 102 ms
76,664 KB |
testcase_27 | AC | 110 ms
77,872 KB |
testcase_28 | AC | 107 ms
76,836 KB |
testcase_29 | AC | 102 ms
76,824 KB |
testcase_30 | AC | 103 ms
76,828 KB |
testcase_31 | AC | 104 ms
76,772 KB |
testcase_32 | AC | 102 ms
76,816 KB |
testcase_33 | AC | 402 ms
143,204 KB |
testcase_34 | AC | 400 ms
143,472 KB |
testcase_35 | AC | 402 ms
143,848 KB |
testcase_36 | AC | 400 ms
144,556 KB |
testcase_37 | AC | 388 ms
143,912 KB |
testcase_38 | AC | 344 ms
141,992 KB |
testcase_39 | RE | - |
testcase_40 | AC | 388 ms
146,060 KB |
testcase_41 | AC | 369 ms
146,936 KB |
ソースコード
""" 多分想定解v1 """ import bisect def LIS(lis): seq = [] for c in lis: ind = bisect.bisect_left(seq,c) if ind == len(seq): seq.append(c) else: seq[ind] = c return len(seq) alp = "abcdefghijklmnopqrstuvwxyz?" cd = {} #文字→数字にする辞書型 for i in range(-1,26): cd[alp[i]] = i #N = int(input()) S = list(input()) #制約チェック #assert N == len(S) for i in S: assert i in cd N = len(S) #全て?の場合を処理する allq = True #全て?かどうかのフラグ for i in S: if i != "?": allq = False break if allq: print ("a"*N) sys.exit() # dp[i][c] = i文字目以降で作れる最長増加部分列のうち、c以上で始まる物の最長。?は無視する dpA = [[0] * 26 for i in range(N+1)] for i in range(N-1,-1,-1): nmax = 0 #dpA[i][c] の最大 (c > j) for j in range(25,-1,-1): dpA[i][j] = max(dpA[i+1][j] , nmax) if cd[S[i]] == j: dpA[i][j] = max(dpA[i][j] , nmax + 1) nmax = max(nmax , dpA[i][j]) OLIS = max(dpA[0]) #?を無視した際のLIS """ for i in dpA: print (*i) print (OLIS) """ ans = [] dpB = [[0] * 26 for i in range(N+1)] #i文字目以前で作れるLISのうち、c以下で終る物の最長 for i in range(N): if S[i] != "?": #?でない場合、置くものは一意 nc = cd[S[i]] else: #?の場合、置ける辞書順最小の物を探索する for c in range(26): if c == 0: if dpA[i+1][c+1] + 1 <= OLIS: nc = c break elif c != 25: if dpB[i-1][c-1] + dpA[i+1][c+1] + 1 <= OLIS: nc = c break else: #25 if dpB[i-1][c-1] + 1 <= OLIS: nc = c break else: print ("error",file=sys.stderr) sys.exit(1) ans.append(alp[nc]) nmax = 0 for j in range(26): dpB[i][j] = max(dpB[i-1][j] , nmax) if nc == j: dpB[i][j] = max(dpB[i][j] , nmax + 1) nmax = max(nmax , dpB[i][j]) assert LIS(ans) == OLIS print ("".join(ans))