D - Logical Filling https://atcoder.jp/contests/abc401/tasks/abc401_d

abc401_d.py

def calc_dp(s):
    # dp[i][0] : s[0..i-1] の文字列で、末尾を '.' にした場合の o の最大数
    # dp[i][1] : s[0..i-1] の文字列で、末尾を 'o' にした場合の o の最大数
    dp = [[-float("inf")] * 2 for _ in range(N + 1)]
    dp[0][0] = 0
    for i in range(N):
        if s[i] != "o":
            dp[i + 1][0] = max(dp[i][0], dp[i][1])
        if s[i] != ".":
            dp[i + 1][1] = dp[i][0] + 1
    return dp


N, K = map(int, input().split())
S = list(input())

ocount = S.count("o")
if ocount == K:
    S = ['.' if c == '?' else c for c in S]
    print("".join(S))
    exit()
    
# 左からのDP
dpl = calc_dp(S)

# 右からのDP
S_rev = S[::-1]
dpr = calc_dp(S_rev)
dpr.reverse()

for i in range(N):
    if S[i] != "?":
        continue
    if max(dpl[i][0], dpl[i][1]) + max(dpr[i + 1][0], dpr[i + 1][1]) < K:
        S[i] = "o"
    elif dpl[i][0] + dpr[i + 1][0] + 1 < K:
        S[i] = "."
        
print("".join(S))