はまやんはまやんはまやん

hamayanhamayan's blog

Dubious Document 2 [AtCoder Beginner Contest 076 C]

http://abc076.contest.atcoder.jp/tasks/abc076_c

解法

(本番通してしまった嘘解法)
http://abc076.contest.atcoder.jp/submissions/1720191
辞書順最小なので、SSの'?'にはできるだけ前に'a'を入れておきたい。
そのため、SS内にTがある必要があるが、これはなるべく後ろで作り、それより前の'?'を'a'にする方針で貪欲する。
後ろからSS内にTを作れるかを全探索し、作れるなら作り、それ以外の'?'は'a'で変換すると答え。
Hackケース

?b??
ab

真の回答
http://abc076.contest.atcoder.jp/submissions/1722356

'?'は全て'a'として、作れるやつを全て作って、辞書順最小のものを答える。

string SS, T;
//---------------------------------------------------------------------------------------------------
string solve() {
    int N = SS.length();
    int M = T.length();
 
    set<string> ans;
    rrep(R, N, M) {
        int L = R - M;
 
        int ok = 1;
        rep(i, 0, M) if (SS[L + i] != '?' and SS[L + i] != T[i]) ok = 0;
        if (ok) {
            string S;
            rep(i, 0, N) S += SS[i];
            rep(i, 0, M) S[L + i] = T[i];
            rep(i, 0, N) if (S[i] == '?') S[i] = 'a';
            ans.insert(S);
        }
    }
 
    if(ans.size() == 0) return "UNRESTORABLE";
    return *(ans.begin());
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> SS >> T;
    cout << solve() << endl;
}