ABC 076 C Dubious Document 2

競技プログラミング

qiita.com

続きです。

atcoder.jp

問題概要

'?'と英字小文字で構成される文字列Sと英字小文字のみで構成される文字列Tが与えられる。'?'を任意の文字とした時、SにTが含まれている(合致する)場合の辞書順最小のSを求めよ。かな？

考えたこと

Tには、Sの後ろで合致して、残った'?'は'a'に変えるのがいいはず。したがって、SとTを反転させて、先頭からO(|S||T|)で検索していく。

詰まったところ

単純に考えたことを実装していって、最初に合致したもののみで、提出すると、1 つだけテストケースが通らない。 結局、Sとなりうる候補のうちから、ソートして、1 つ提出するというものにしたら通った。

おそらく、S="??e???"、T="ecc"とすると、解は、"aaecca" だと思われるが、算出されるのは、"aaeecc"になってしまうからだと思われる。正直、反例をあげるのが、精一杯だ。数弱が出てしまった。

以下、解

def main():
    s = "".join(reversed(list(input())))
    t = "".join(reversed(list(input())))
    anses = []

    for i in range(len(s)):
        for j in range(len(t)):
            if i+j < len(s) and (s[i+j] == t[j] or s[i+j] == '?'):
                continue
            else:
                break
        else:
            # 合っていた
            ans = (s[:i]+t+s[i+len(t):]).replace('?', 'a')
            anses.append("".join(reversed(list(ans))))
            continue
    anses.sort()
    print(anses[0] if anses else "UNRESTORABLE")

if __name__ == '__main__':
    main()

個人的に貪欲より全探索の方がメインの問題だった。