#656043 (PyPy3) No.1609 String Division Machine

• 問題: No.1609 String Division Machine
• ユーザー: 👑 SPD_9X2
• 提出日時: 2021-05-10 23:28:20
• 言語: PyPy3 (7.3.15)
• 結果: RE
• 実行時間: -
• コード長: 2,260 bytes
• コンパイル時間: 357 ms
• コンパイル使用メモリ: 82,460 KB
• 実行使用メモリ: 145,192 KB
• 最終ジャッジ日時: 2024-07-06 07:53:05
• 合計ジャッジ時間: 5,632 ms
• ジャッジサーバーID （参考情報）: judge5 / judge3

ファイルパターン	結果
sample	AC * 4 RE * 1
other	AC * 35 RE * 2

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
"""
多分想定解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))
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX