結果
問題 | No.1609 String Division Machine |
ユーザー | 👑 SPD_9X2 |
提出日時 | 2021-05-10 23:50:15 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 405 ms / 2,000 ms |
コード長 | 2,305 bytes |
コンパイル時間 | 318 ms |
コンパイル使用メモリ | 86,948 KB |
実行使用メモリ | 147,020 KB |
最終ジャッジ日時 | 2023-09-20 12:33:19 |
合計ジャッジ時間 | 8,394 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 78 ms
71,456 KB |
testcase_01 | AC | 73 ms
71,316 KB |
testcase_02 | AC | 73 ms
71,096 KB |
testcase_03 | AC | 79 ms
71,272 KB |
testcase_04 | AC | 78 ms
71,300 KB |
testcase_05 | AC | 77 ms
71,344 KB |
testcase_06 | AC | 77 ms
71,148 KB |
testcase_07 | AC | 88 ms
76,664 KB |
testcase_08 | AC | 87 ms
76,588 KB |
testcase_09 | AC | 75 ms
71,556 KB |
testcase_10 | AC | 82 ms
71,264 KB |
testcase_11 | AC | 85 ms
76,444 KB |
testcase_12 | AC | 77 ms
71,292 KB |
testcase_13 | AC | 90 ms
76,772 KB |
testcase_14 | AC | 92 ms
76,492 KB |
testcase_15 | AC | 89 ms
76,616 KB |
testcase_16 | AC | 91 ms
76,636 KB |
testcase_17 | AC | 93 ms
76,780 KB |
testcase_18 | AC | 93 ms
76,676 KB |
testcase_19 | AC | 92 ms
76,744 KB |
testcase_20 | AC | 93 ms
76,772 KB |
testcase_21 | AC | 91 ms
76,768 KB |
testcase_22 | AC | 91 ms
76,764 KB |
testcase_23 | AC | 103 ms
76,708 KB |
testcase_24 | AC | 104 ms
76,712 KB |
testcase_25 | AC | 101 ms
76,692 KB |
testcase_26 | AC | 104 ms
76,784 KB |
testcase_27 | AC | 112 ms
77,956 KB |
testcase_28 | AC | 106 ms
76,704 KB |
testcase_29 | AC | 104 ms
76,588 KB |
testcase_30 | AC | 103 ms
76,964 KB |
testcase_31 | AC | 105 ms
77,020 KB |
testcase_32 | AC | 103 ms
76,544 KB |
testcase_33 | AC | 405 ms
143,320 KB |
testcase_34 | AC | 390 ms
143,500 KB |
testcase_35 | AC | 402 ms
143,792 KB |
testcase_36 | AC | 400 ms
144,512 KB |
testcase_37 | AC | 394 ms
143,768 KB |
testcase_38 | AC | 348 ms
141,808 KB |
testcase_39 | AC | 85 ms
77,264 KB |
testcase_40 | AC | 389 ms
146,092 KB |
testcase_41 | AC | 368 ms
147,020 KB |
ソースコード
""" 想定解v2 エラー解消 """ import bisect import sys 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) assert 1 <= N <= 10**5 #全て?の場合を処理する 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))