Atcoder Problems という競プロを勉強する上でのコンテンツがあります。URL
今回は、hard100問の内6問目を解説していきたいと思います。
問題名 【C – Dubious Document 2】
入力
S’：文字列
T : 文字列
考察
今回辞書順最小にしたいので、先頭がaから始まると嬉しく、逆を言うと、後ろとかにzとかがあっても辞書順は、あまり変化しません。
例えば、
S' = ?tc????
T = z
の場合、ztcaaaa よりも、atcaaazのほうが辞書順は早いです。
なので、S’を後ろから見ていき、Tが当てはまったら代入し、それ以外の?をaに置換すれば良いです。
(最後まで、Tが当てはまらなかったらUNRESTORABLEを出力)
もう少しだけ楽をしたい
しかし、後ろから当てはめていくのは、実装が少し面倒です。
なので、s’ と T をそれぞれリバースして、前から当てはめていき、作成された文字列Sを再度リバースして、出力します
コード
import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def II(): return int(sys.stdin.readline())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def S(): return sys.stdin.readline().rstrip()
readline = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
s = S()
T = S()
reversed_s = s[::-1]
reversed_t = T[::-1]
cnt = 0
#何文字一致したかをカウントする
for i in range(len(reversed_s)-len(reversed_t)+1):
for j in range(len(reversed_t)):
#反転させたs'が ? or 反転させたTの文字列が一致したら
if reversed_s[i+j] == '?' or reversed_s[i+j] == reversed_t[j]:
#一致した文字列をカウントを+1する
cnt += 1
if cnt == len(reversed_t):
#一致した文字列がTの文字列分になったら
ans = reversed_s[:i] + reversed_t + reversed_s[i+len(reversed_t):]
# 答えとなる文字列を作成
ans = ans[::-1]
# 文字列を反転
print(ans.replace('?', 'a'))
exit()
else:
##一致しなかったら何文字一致したかのカウントをリセットする
cnt = 0
break
print("UNRESTORABLE")まとめ
本当は尺取法とかのほうがよいけど、今回は計算量に余裕があるので、よきかな
前の問題【D – Powerful Discount Tickets】
次の問題【E – Double Factorial】
コメント