はじめに
競プロの精進のために学びがあった問題についてまとめています。 目標は AtCoder 水色!
今のレートは茶色です。
問題
ABC076 C – Dubious Document 2を解きました。
難易度は緑色。
考察
後方から貪欲的に一致する文字列を探していって、最初に見つかったもの以外の?はすべて”a”で埋めると辞書順最小になる。
サンプルは通ったが、「len(Sd) と len(T)」の長さが一致した場合の考慮漏れで1ペナしてしまったので大いに反省。
コード
Sd = input()[::-1]
T = input()[::-1]
for i in range(len(Sd) + 1 - len(T)):
f = True
for j, t in enumerate(T):
if t != Sd[i+j] and Sd[i+j] != '?':
f = False
break
if f:
ans = []
for k in range(len(Sd)):
if Sd[k] == '?':
ans.append("a")
else:
ans.append(Sd[k])
for j, t in enumerate(T):
ans[i+j] = t
print("".join(ans[::-1]))
exit()
print("UNRESTORABLE")
まとめ
ペナ予防のために、範囲の端と端を含むかちゃんと確認する。