Problem p02664 (python)

Fixed submission:
inf = float("inf")

S = input()



N = len(S)
bestP = [None for i in range(N)]
bestD = [None for i in range(N)]
if S[0] in ["?", "D"]:
    bestP[0] = 0
    bestD[0] = 1
else:
    bestP[0] = 0
    bestD[0] = 0
for i in range(1, N):
    bestP[i] = max(bestD[i - 1], bestP[i - 1])
    bestD[i] = max(bestD[i - 1] + 1, bestP[i - 1] + 2)
    if S[i] != "?":
        if S[i] == "P":
            bestD[i] = -inf
        else:
            assert S[i] == "D"
            bestP[i] = -inf

ans = [None for i in range(N)]
if bestP[-1] > bestD[-1]:
    ans[-1] = 'P'
else:
    ans[-1] = 'D'
for i in range(N - 2, -1, -1):
    if S[i] != '?':
        ans[i] = S[i]
    else:
        prev = ans[i + 1]
        if prev == 'D':
            if bestP[i] + 2 > bestD[i] + 1:
                ans[i] = 'P'
            else:
                ans[i] = 'D'
        else:
            if bestP[i] > bestD[i]:
                ans[i] = 'P'
            else:
                ans[i] = 'D'

print(''.join(ans))

Buggy submission (verdict: Runtime Error):
(N,) = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

numLeafs = A

# Bound max non-leaves by how many expansions the previous level can do
maxNonLeafs = [None for i in range(N + 1)]
maxNonLeafs[0] = 1
for i in range(1, N + 1):
    maxNonLeafs[i] = 2 * maxNonLeafs[i - 1] - numLeafs[i]
# Tighten max non-leaves by how many available children are on next level
maxNonLeafs[N] = 0
for i in range(N - 1, -1, -1):
    maxNonLeafs[i] = min(maxNonLeafs[i], maxNonLeafs[i + 1] + numLeafs[i + 1])

# Bound min non-leaves by how many expansions are needed for the next level
minNonLeafs = [None for i in range(N + 1)]
minNonLeafs[N] = 0
for i in range(N - 1, -1, -1):
    # The minimum non-leafs of each level is at least half (round up) of number of nodes on next level
    minNonLeafs[i] = (minNonLeafs[i + 1] + numLeafs[i + 1] + 1) // 2
    # Make sure valid
    if minNonLeafs[i] + numLeafs[i] > 2 ** i:
        print(-1)
        exit()

count = 0
for i in range(N + 1):
    count += maxNonLeafs[i] + numLeafs[i]
print(count)

Buggy submission (verdict: Runtime Error):
S = input()


def makeRepeat(arr):
    repeat = [[arr[0], 0]]
    for x in arr:
        if x == repeat[-1][0]:
            repeat[-1][1] += 1
        else:
            repeat.append([x, 1])
    return repeat


ans = []
repeats = makeRepeat(S)
for i, (ch, count) in enumerate(repeats):
    if ch != "?":
        ans.append(ch * count)
    else:
        if i - 1 >= 0:
            prev = repeats[i - 1][0]
        nxt = None
        if i + 1 < len(repeats):
            nxt = repeats[i + 1][0]

        if prev == "P":
            q, r = divmod(count, 2)
            ans.append("DP" * q + "D" * r)
        elif nxt == "D":
            q, r = divmod(count, 2)
            ans.append("P" * r + "DP" * q)
        else:
            ans.append("D" * count)

print("".join(ans))

Buggy submission (verdict: Runtime Error):
S = input()


def makeRepeat(arr):
    repeat = [[arr[0], 0]]
    for x in arr:
        if x == repeat[-1][0]:
            repeat[-1][1] += 1
        else:
            repeat.append([x, 1])
    return repeat


ans = []
repeats = makeRepeat(S)
for i, (ch, count) in enumerate(repeats):
    if ch != "?":
        ans.append(ch * count)
    else:
        if i - 1 >= 0:
            prev = S[i - 1]
        nxt = None
        if i + 1 < len(repeats):
            nxt = S[i + 1]

        if prev == "P":
            q, r = divmod(count, 2)
            ans.append("DP" * q + "D" * r)
        elif nxt == "D":
            q, r = divmod(count, 2)
            ans.append("P" * r + "DP" * q)
        else:
            ans.append("D" * count)

print("".join(ans))